Maximum Total Length of Non-Overlapping Intervals
Bloomberg LP● MediumNEW GRADONSITE INTERVIEWProblem statement
Given an array of half-open intervals [start, end), choose a pairwise non-overlapping subset whose total covered length is maximum. Two intervals are compatible when one interval's end is less than or equal to the other's start.
Return the chosen intervals sorted by increasing start, breaking ties by increasing end. The input is guaranteed to have a unique maximum-total-length subset.
Function
maximumLengthIntervals(intervals: int[][]) → int[][]Examples
Example 1
intervals = [[1,4],[3,6],[5,10],[6,8]]return = [[1,4],[5,10]]The two returned intervals do not overlap and have total length 3 + 5 = 8, which is maximal.
Example 2
intervals = [[0,10],[1,4],[4,8]]return = [[0,10]]The long interval contributes length 10, exceeding the compatible pair's total length of 7.
Example 3
intervals = [[1,3],[3,7],[2,6]]return = [[1,3],[3,7]]Touching half-open intervals are compatible, so the first two provide total length 6.
Constraints
1 <= intervals.length <= 10000intervals[i].length == 20 <= intervals[i][0] < intervals[i][1] <= 1000000000- The maximum-total-length compatible subset is unique.