Merging Meeting Times

mediumSave

ArrayIntervalsSorting

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.

Example 1

Input

Output

[[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.

Example 2

Input

Output

[[1, 5]]

Explanation. Intervals [1,4] and [4,5] touch at the end/start, so they are merged into [1,5].

Example 3

Input

Output

[[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?

Constraints:

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: 2