- 1. Problem Description
- 2. System Design
- 3. Algorithm
Max Coverage of Segments
Given a total of N elements, find the largest coverage we can get after removing one segment.
Input: [[5,9], [1,4], [3,7]]
Explanation: By removing [3,7], the remaining segments covers a total length of 7
Input format: the first line contains the length of the array; all following lines are the start and end of segments.
The example above corresponds to:
3 5 9 1 4 3 7
Segment class represents a segment (as a line in the input file), with a
start and an
This class is designed to be a hashable and immutable model class (although the immutability usually cannot be enforced in Python).
In addition to
equals, it provides several useful functions:
|Returns the size of the segment|
|Tells if the current segment covers another segment|
|Tells if the current segment overlaps with another segment|
|Return the intersection segment of the current and another segment|
FileEngine object is in charge of a pair of input/output files.
An instance can be created by
FileEngine(file_id), and it provides two functions:
|Read the raw input file and return a list of |
|Write an integer to the output file|
First, we sort the
Segments array according to their start time. This can be achieved in $O(n log(n))$ time.
Then, for each
Segment object in the sorted array, we remove all following segments that it covers. This can be achieved in $O(n)$ time.
If there exists an
segments[i] such that
segments[i-1] overlaps with
segments[i+1], we call
segments[i] “redundant”, because the overall coverage will NOT be affected after it is removed.
If a redundant segment is found, we simply calculate and return the coverage of the remaining segments.
After pre-processing, we have a segment array with some special properties.
Consider any three consecutive segments in the array,
segments[i+1], the following properties can be ensured:
|NO redundancy (in other words, |
With such properties, the coverage of remaining segments after removing a
segments[i] can be calculated by an addition of:
- Total coverage from
- Total coverage from
The core algorithm uses a two-pass dynamic programming technique, once forward and another backward.
There are two arrays:
forward[i] stores the total coverage from
backward[i] stores the total coverage from
segments[-1] (both ends included).
Hence, the first element in
forward should be the
size() of the first segment.
Then, from the second segment, for each
segments[i], we compute the combined total coverage up until that element,
forward[i], using three values we already have:
segments[i] does NOT overlap, the current total coverage
forward[i] can be calculated by
forward[i-1] + segments[i].size().
Otherwise, we need to calculate the
intersection by calling
segments[i].intersection(segments[i-1]), and then
forward[i] = forward[i-1] + segments[i].size() + intersection.size()
After we fill up the
forward array, we do the same in the reverse order to generate the
Once we have both the
backward arrays, finding the maximum coverage is super easy. For any element in between (not the first/last), the total coverage without it is simply
forward[i-1] + backward[i+1].
Finally, we compare all coverages above and
backward to get the maximum.