LeetCode Meditations: Merge Intervals

Let's start with the description for Merge Intervals:

Given an array of 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.

For example:

Input: intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
Output: [[1, 6], [8, 10], [15, 18]]

Explanation: Since intervals [1, 3] and [2, 6] overlap, merge them into [1, 6].

Or:

Input: intervals = [[1, 4], [4, 5]]
Output: [[1, 5]]

Explanation: Intervals [1, 4] and [4, 5] are considered overlapping. 

---

We can start by sorting the intervals first, so that we can compare them easily later:

intervals.sort((a, b) => a[0] - b[0]);

Also, we can initialize a result array which initially holds the first element of the newly sorted intervals:

let result = [intervals[0]];

We need to track the last merged interval's end to compare it with the start of the current interval we are looking at to check if they overlap.

Note

For two intervals not to overlap, the

Note

For two intervals not to overlap, the start of one should be strictly larger than the end of the other or the end of the one should be strictly smaller than the start of the other, as mentioned in our chapter introduction.

start of one should be strictly larger than the end of the other or the end of the one should be strictly smaller than the start of the other, as mentioned in our chapter introduction.

If they don't overlap, we can just add that interval to result. Otherwise, we need to update the "last end," effectively merging the intervals:

Input: intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
Output: [[1, 6], [8, 10], [15, 18]]

Explanation: Since intervals [1, 3] and [2, 6] overlap, merge them into [1, 6].

And, the only thing left to do is to return the result:

Input: intervals = [[1, 4], [4, 5]]
Output: [[1, 5]]

Explanation: Intervals [1, 4] and [4, 5] are considered overlapping. 

And, this is how our final solution looks like in TypeScript:

intervals.sort((a, b) => a[0] - b[0]);

Time and space complexity

We are sorting intervals, and the built-in sort function has $O(nlogn)$O(n log n) time complexity. (The looping is $O(n)$O(n) , but the overall time complexity is $O(nlogn)$O(n log n) ).

The result array can increase in size as the size of the input array intervals increases, therefore we have $O(n)$O(n) space complexity.

---

Next up, we'll take a look at the last problem in the chapter, Non-overlapping Intervals. Until then, happy coding.

The above is the detailed content of LeetCode Meditations: Merge Intervals. For more information, please follow other related articles on the PHP Chinese website!