Two Bus Runs Off the Board
Indices of two intervals whose removal minimizes remaining union length
A city bus network has several scheduled runs serving the same corridor. Run i provides service throughout the half-open time interval [runs[i][0], runs[i][1]).
The corridor has service at a time whenever at least one retained run is operating. Its covered duration is the total length of the union of all retained runs' intervals; overlapping service is counted only once.
The dispatcher must cancel exactly two distinct runs. Choose the cancellations that minimize the covered duration remaining afterward.
Return the two canceled runs' original zero-based indices in increasing order. If several pairs leave the same minimum covered duration, return the lexicographically smallest pair: prefer the smaller first index, then the smaller second index.
Runs are listed in arbitrary order. Two runs with identical intervals are still distinct runs. Intervals that only touch at an endpoint do not overlap.
Examples
Example 1
Input: runs = [[0,5],[3,8],[10,14]] Output: [0,1]
The first two runs overlap, while the final run is separate. Canceling a run may remove only its exclusive portion if another retained run still covers the overlap.
Example 2
Input: runs = [[0,10],[0,10],[20,21]] Output: [0,1]
The two identical runs protect each other's entire service window. Canceling both removes that window, whereas canceling just one does not.
Example 3
Input: runs = [[8,10],[-2,0],[3,5],[12,14]] Output: [0,1]
These disjoint runs have equal durations, so every cancellation pair leaves the same covered duration. The index tie-breaking rule determines the answer.
Constraints
- 2 <= len(runs) <= 3000
- Each runs[i] contains exactly two integers: a start and an end.
- -10^9 <= runs[i][0] < runs[i][1] <= 10^9
The intended solution uses O(n log n) time and O(n) auxiliary space. All durations and tie comparisons are exact integers.
Hints
Show hint 1Hint 1
For any positive-length span between consecutive endpoints, canceling two runs can remove coverage only if that span currently has one or two active runs.
Show hint 2Hint 2
Accumulate exclusive duration for each run and shared duration for each exact pair of active runs. Only linearly many distinct pairs can receive a nonzero shared contribution.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you also return the minimum remaining covered duration without changing the asymptotic complexity?
- If the dispatcher could cancel exactly three runs, which coverage contributions would matter, and why is choosing the best triple more difficult?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem