56. Merge Intervals
Problem Description
The given problem requires us to merge all the overlapping intervals in a list. An interval is represented as a list with two elements where the first element is the start and the second is the end of the interval ([start, end]
). An "overlap" occurs when one interval's start is less than or equal to the end of another interval. The goal is to simplify the list of intervals to a list where no intervals overlap, ensuring that the new list collectively spans the same range as the original intervals.
Here's an example for clarification:
Original list of intervals: [[1,3],[2,6],[8,10],[15,18]]
After merging all the overlapping intervals, we get: [[1,6],[8,10],[15,18]]
In the merged intervals, there is no pair of intervals such that one overlaps with another.
Intuition
The intuition behind the solution comes from two realizations:
- If we sort the intervals based on their start times, any overlapping intervals will be placed next to each other in the list.
- To merge intervals, we only need to track the end time since the sorted order ensures that the next interval's start time is always greater than or equal to the current interval's start time.
The approach is as follows:
- Sort the list of intervals based on their start times.
- Initialize a new list to hold the merged intervals and add the first interval to it.
- Iterate through the rest of the intervals, and for each one, compare its start time with the end time of the last interval in the merged list.
- If the start time is greater than the end time of the last interval in the merged list, then there is no overlap, and we can add the current interval as a new entry to the merged list.
- If there is overlap (the start time is less than or equal to the end time), we update the end time of the last interval in the merged list to be the maximum of the end times of the last interval and the current interval.
- The process continues until we have gone through all the intervals.
- We return the merged list of intervals as the answer.
This solution guarantees that we merge all overlapping intervals and result in a list of intervals with no overlaps.
Learn more about Sorting patterns.
Solution Approach
The solution to the problem involves sorting the intervals and then iterating through the sorted list to merge any overlapping intervals.
Here's a step-by-step breakdown of the implementation:
-
First, we sort the given list of intervals. This is done in-place using the native sort function provided by Python, which sorts the intervals based on their first element (the start times).
intervals.sort()
By sorting the intervals, we are able to take advantage of the fact that any intervals that might need merging will appear next to each other in the list.
-
We then initialize a new list called
ans
, which will store our merged intervals, and we start by adding the first interval to it.ans = [intervals[0]]
This acts as a comparison base for merging subsequent intervals.
-
We then proceed to iterate over the rest of the intervals, starting from the second interval onward, to check for overlapping with the currently last interval in our
ans
list.for s, e in intervals[1:]:
Here,
(s, e)
represents the start and end times of the current interval we are looking at. -
If the start time
s
of the current interval is greater than the end time of the last interval inans
, it means there is no overlap and we can simply add this interval toans
.if ans[-1][1] < s: ans.append([s, e])
-
However, if an overlap exists, we need to merge the current interval with the last interval in
ans
. To do this, we update the end time of the last interval inans
with the maximum end time between the two overlapping intervals.else: ans[-1][1] = max(ans[-1][1], e)
This ensures that the intervals are merged, covering the overlapping time spans without duplicating intervals.
-
Once we finish iterating through all intervals, the
ans
list contains the merged intervals. We returnans
as the final set of non-overlapping intervals.
The algorithm uses the sort-merge pattern, which is common for interval problems. By sorting and then merging, we bring the overall run-time complexity down to O(N log N) where N is the number of intervals, with the sort contributing to the log N factor and the merge process being linear in nature. Regarding data structures, the solution leverages lists and the use of tuple unpacking for readability.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's take a small example to illustrate the solution approach with the provided intervals: [[5,7],[1,3],[3,4],[2,6]]
.
Sorting the Intervals
First, we need to sort the intervals by their starting points to align any intervals that might overlap:
Before sort: [[5,7],[1,3],[3,4],[2,6]] After sort: [[1,3],[2,6],[3,4],[5,7]]
We used intervals.sort()
to achieve this.
Initializing and Iterating for Merging
We then initialize the ans
list with the first sorted interval, treating it as the base for our merged intervals:
ans = [[1,3]]
Next, we start iterating from the second element of the sorted intervals:
-
We look at
[2,6]
and compare it to the last element ofans
, which is[1,3]
. Since the start2
is within[1,3]
(as3
is greater than2
), they overlap. We merge them by updating the end of the last interval inans
to the max end of both intervals, nowans
becomes[[1,6]]
. -
Proceeding to
[3,4]
, we compare it to the last element[1,6]
. Again, it overlaps because4
is not greater than6
. No need to change the end time since6
is already the maximum end. -
Finally, we look at
[5,7]
. This does not overlap with[1,6]
as5
is not greater than6
. Since7
is greater than6
, we add[5,7]
as a new interval toans
. After the addition,ans
becomes[[1,6],[5,7]]
.
However, our merging logic must have the current start to be greater than the last end to avoid overlap. Therefore, we should adjust the last step:
[5,7]
is checked again and it actually overlaps with[1,6]
(since5
is less than or equal to6
). We merge them by updating the end of the last interval inans
to7
, andans
now becomes[[1,7]]
.
Final Merged List
Having completed the iteration over the sorted intervals, we have a list of merged intervals where no two intervals overlap. The final ans
is:
[[1,7]]
This means we successfully merged all intervals to cover the same range without having any overlapping intervals. The solution approach, by sorting and then merging, streamlined the process and ensures an efficient way to obtain the merged intervals.
Solution Implementation
1class Solution:
2 def merge(self, intervals: List[List[int]]) -> List[List[int]]:
3 # Sort the interval list based on the start times of intervals
4 intervals.sort()
5
6 # Initialize the merged_intervals list with the first interval
7 merged_intervals = [intervals[0]]
8
9 # Iterate over the intervals, starting from the second interval
10 for start, end in intervals[1:]:
11 # Check if the current interval does not overlap with the last interval in merged_intervals
12 if merged_intervals[-1][1] < start:
13 # If it does not overlap, add the current interval to merged_intervals
14 merged_intervals.append([start, end])
15 else:
16 # If it does overlap, merge the current interval with the last one by
17 # updating the end time of the last interval to the maximum end time seen so far
18 merged_intervals[-1][1] = max(merged_intervals[-1][1], end)
19
20 # Return the merged intervals
21 return merged_intervals
22
1import java.util.Arrays;
2import java.util.List;
3import java.util.ArrayList;
4
5class Solution {
6
7 // Method to merge overlapping intervals.
8 public int[][] merge(int[][] intervals) {
9 // Sort the intervals by their starting times.
10 Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
11
12 // List that holds the merged intervals.
13 List<int[]> mergedIntervals = new ArrayList<>();
14 // Add the first interval to the list as starting interval for merging.
15 mergedIntervals.add(intervals[0]);
16
17 // Loop through all the intervals starting from the second one.
18 for (int i = 1; i < intervals.length; ++i) {
19 // Get the start and end times of the current interval.
20 int start = intervals[i][0];
21 int end = intervals[i][1];
22
23 // Get the last interval in the merged list.
24 int[] lastMergedInterval = mergedIntervals.get(mergedIntervals.size() - 1);
25
26 // Check if there is an overlap with the last interval in the merged list.
27 if (lastMergedInterval[1] < start) {
28 // No overlap, so we can add the current interval as it is.
29 mergedIntervals.add(intervals[i]);
30 } else {
31 // Overlap exists, so we extend the last interval's end time.
32 lastMergedInterval[1] = Math.max(lastMergedInterval[1], end);
33 }
34 }
35
36 // Convert the merged intervals list to a 2D array and return it.
37 return mergedIntervals.toArray(new int[mergedIntervals.size()][]);
38 }
39}
40
1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6 // Function to merge overlapping intervals
7 std::vector<std::vector<int>> merge(std::vector<std::vector<int>>& intervals) {
8 // First, sort the intervals based on the starting times
9 std::sort(intervals.begin(), intervals.end());
10
11 // This will be the result vector for merged intervals
12 std::vector<std::vector<int>> mergedIntervals;
13
14 // Initialize the result vector with the first interval
15 mergedIntervals.push_back(intervals[0]);
16
17 // Iterate through all the intervals starting from the second one
18 for (int i = 1; i < intervals.size(); ++i) {
19 // If the current interval does not overlap with the last interval in the result,
20 // then simply add the current interval to the result
21 if (mergedIntervals.back()[1] < intervals[i][0]) {
22 mergedIntervals.push_back(intervals[i]);
23 } else {
24 // If there is an overlap, merge the current interval with the last interval
25 // in the result by updating the end time to the maximum end time seen
26 mergedIntervals.back()[1] = std::max(mergedIntervals.back()[1], intervals[i][1]);
27 }
28 }
29 // Return the merged intervals
30 return mergedIntervals;
31 }
32};
33
1function merge(intervals: number[][]): number[][] {
2 // First, we sort the intervals array based on the start times
3 intervals.sort((a, b) => a[0] - b[0]);
4
5 // Initialize the merged intervals array with the first interval
6 const mergedIntervals: number[][] = [intervals[0]];
7
8 // Iterate through the intervals starting from the second element
9 for (let i = 1; i < intervals.length; ++i) {
10 // Get the last interval in the mergedIntervals array
11 const lastInterval = mergedIntervals[mergedIntervals.length - 1];
12
13 // If the current interval does not overlap with the last interval in mergedIntervals
14 if (lastInterval[1] < intervals[i][0]) {
15 // Add the current interval to the mergedIntervals array as it cannot be merged
16 mergedIntervals.push(intervals[i]);
17 } else {
18 // If there is an overlap, merge the current interval with the last interval
19 // by updating the end time of the last interval to the maximum end time
20 lastInterval[1] = Math.max(lastInterval[1], intervals[i][1]);
21 }
22 }
23
24 // Return the array containing all the merged intervals
25 return mergedIntervals;
26}
27
Time and Space Complexity
Time Complexity
The given code has two main operations:
- Sorting the
intervals
list. - Iterating through the sorted list and merging overlapping intervals.
For a list of n
intervals:
- The sort operation typically has a complexity of
O(n log n)
, since Python uses TimSort (a hybrid sorting algorithm derived from merge sort and insertion sort) for sorting lists. - The iteration over the list has a complexity of
O(n)
, because we go through the intervals only once.
Hence, the total time complexity is the sum of these two operations, which is O(n log n) + O(n)
. Since O(n log n)
is the higher order term, it dominates the total time complexity, which simplifies to O(n log n)
.
Space Complexity
The space complexity consists of the additional space used by the algorithm apart from the input:
- The
ans
list which contains the merged intervals is the main additional data structure used, and in the worst case, if no intervals overlap, it will containn
intervals. - Since the
ans
list reuses the intervals from the original input list, and the input list size itself is not included in the additional space used for computing space complexity, the space used to storeans
can be consideredO(1)
(constant space) in this context.
Thus, the space complexity is O(1)
.
Learn more about how to find time and space complexity quickly using problem constraints.
How does merge sort divide the problem into subproblems?
Recommended Readings
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!