Maximum Non-Overlapping Longer Intervals
Bloomberg LP● MediumNEW GRADONSITE INTERVIEWProblem statement
Treat intervals as half-open [start,end). Consider them by descending length, breaking ties by ascending start then end. Accept an interval when it does not overlap any already accepted interval.
Return the resulting maximal accepted set sorted by start then end.
Function
prioritizeLongerIntervals(intervals: int[][]) → int[][]Examples
Example 1
intervals = [[0,10],[0,4],[4,8],[10,12]]return = [[0,10],[10,12]]The length-ten interval is accepted first and blocks both shorter contained intervals.
Constraints
0 <= intervals.length <= 2000.start < end.