Merging Meeting Times
Given an array of meeting time intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.
[ [ 1, 3 ], [ 2, 6 ], [ 8, 10 ], [ 15, 18 ] ]
[ [ 1, 6 ], [ 8, 10 ], [ 15, 18 ] ]
Explanation. Intervals [1,3] and [2,6] overlap, merge them into [1,6]. No other overlaps exist, so we include the other intervals as they are.
[ [ 1, 4 ], [ 4, 5 ] ]
[ [ 1, 5 ] ]
Explanation. Intervals [1,4] and [4,5] touch at the end/start, so they are merged into [1,5].
[ [ 10, 12 ], [ 14, 16 ], [ 4, 7 ], [ 18, 20 ], [ 7, 14 ] ]
[ [ 4, 16 ], [ 18, 20 ] ]
Explanation. The intervals [4, 7] and [7, 14] overlap with each other and with [14, 16], all three are merged into [4, 16]. Then [18, 20] stands alone.
Follow-up: Can you implement the solution in a way that it first sorts the intervals by their start time? What would be the implications on time complexity?
1. The input list is not necessarily sorted.\n2. Each interval's end time will always be greater than or equal to the start time.
- Views
- 13