Leetcode 56. Merge Intervals
Problem Explanation:
The problem is to merge all overlapping intervals in a collection of intervals. An interval is represented as a vector of two integers where the first integer of an interval is always less than or equal to the second integer. For instance, if we have intervals [1,3], [2,6], [8,10], [15,18], then the intervals [1,3] and [2,6] are overlapping because 3 >= 2. Therefore, these two intervals are merged into [1,6].
Let's walk through the example 1:
1 2 3Input: [[1,3],[2,6],[8,10],[15,18]] 4 5 * The first interval is [1,3]. 6 * The second interval is [2,6]. It overlaps with previous interval because 3 >= 2. Therefore, these two intervals are merged into [1,6]. 7 * The subsequent intervals [8,10] and [15,18] don't overlap with any interval, so they are added as it is. 8 9Output: [[1,6],[8,10],[15,18]]
Solution Approach:
The solution to this problem involves sorting and then iterating over the collection of intervals.
The first step is to sort each interval by the starting integer in ascending order. The reason for the sorting is to make sure that the start of the next interval is always greater than or equal to the start of the current interval.
Then, we iterate over each of the sorted intervals. If the end of the last interval in the output is greater than or equal to the start of the current interval, it means the current interval overlaps with the last interval in the output. In that case, we merge the current interval with the last interval in the output by updating the end of the last interval to be the maximum of the ends of the last interval in the output and the current interval.
If the current interval does not overlap with the last interval in the output, we simply add the current interval to the output.
Finally, we return the output, which contains all the merged intervals.
Python Solution:
1 2python 3class Solution: 4 def merge(self, intervals): 5 intervals.sort(key = lambda x: x[0]) 6 merged = [] 7 for i in intervals: 8 if not merged or merged[-1][1] < i[0]: 9 merged.append(i) 10 else: 11 merged[-1][1] = max(merged[-1][1], i[1]) 12 return merged
Java Solution:
1 2java 3import java.util.*; 4class Solution { 5 public int[][] merge(int[][] intervals) { 6 if (intervals.length <= 1) 7 return intervals; 8 9 Arrays.sort(intervals, (arr1, arr2) -> Integer.compare(arr1[0], arr2[0])); 10 11 List<int[]> output = new ArrayList<>(); 12 int[] current_interval = intervals[0]; 13 output.add(current_interval); 14 15 for (int[] interval : intervals) { 16 int current_begin = current_interval[0]; 17 int current_end = current_interval[1]; 18 int next_begin = interval[0]; 19 int next_end = interval[1]; 20 21 if (current_end >= next_begin) { 22 current_interval[1] = Math.max(current_end, next_end); 23 } 24 else { 25 current_interval = interval; 26 output.add(current_interval); 27 } 28 } 29 30 return output.toArray(new int[output.size()][]); 31 } 32}
JavaScript Solution:
1
2javascript
3class Solution {
4 merge(intervals) {
5 intervals.sort((a, b) => a[0] - b[0])
6 let merged = []
7 for (let i of intervals) {
8 if (!merged.length || merged[merged.length-1][1] < i[0]) {
9 merged.push(i)
10 }
11 else {
12 merged[merged.length-1][1] = Math.max(merged[merged.length-1][1], i[1])
13 }
14 }
15 return merged
16 }
17}
C++ Solution:
1
2cpp
3class Solution {
4public:
5 vector<vector<int>> merge(vector<vector<int>>& intervals) {
6 vector<vector<int>> merged;
7 if(intervals.size() == 0)
8 return merged;
9 sort(intervals.begin(), intervals.end());
10 vector<int> tempInterval = intervals[0];
11 for(auto it : intervals) {
12 if(it[0] <= tempInterval[1]) {
13 tempInterval[1] = max(it[1], tempInterval[1]);
14 }
15 else {
16 merged.push_back(tempInterval);
17 tempInterval = it;
18 }
19 }
20 merged.push_back(tempInterval);
21 return merged;
22 }
23};
C# Solution:
1 2csharp 3public class Solution { 4 public int[][] Merge(int[][] intervals) { 5 if (intervals.Length <= 1) 6 return intervals; 7 8 List<int[]> output = new List<int[]>(); 9 int[] current_interval = intervals[0]; 10 Array.Sort(intervals, (a, b) => a[0] - b[0]); 11 output.Add(current_interval); 12 13 foreach (var interval in intervals) { 14 int current_end = current_interval[1]; 15 int next_begin = interval[0]; 16 int next_end = interval[1]; 17 18 if (current_end >= next_begin) 19 current_interval[1] = Math.Max(current_end, next_end); 20 else { 21 current_interval = interval; 22 output.Add(current_interval); 23 } 24 } 25 return output.ToArray(); 26 } 27}
Go Solution:
In Go, we first sort the intervals by the start value using the sort.Slice
function. Then we create a merged
slice to store the merged intervals. We execute a loop where we use the len
function to get the last interval in the merged
slice. If itโs not empty and its end is greater than or equal to the start of the new interval, then the intervals overlap. Therefore, we update the end of the last interval in the merged
slice to be the maximum of the end of the last interval and the end of the new interval. If the intervals donโt overlap, we simply append the new interval to the merged
slice. Finally, we return the merged
value.
Go Solution:
1 2go 3package main 4import ( 5 "sort" 6) 7 8func merge(intervals [][]int) [][]int { 9 sort.Slice(intervals, func(i, j int) bool { 10 return intervals[i][0] < intervals[j][0] 11 }) 12 merged := [][]int{} 13 for _, interval := range intervals { 14 if len(merged) == 0 || merged[len(merged)-1][1] < interval[0] { 15 merged = append(merged, interval) 16 } else { 17 merged[len(merged)-1][1] = max(merged[len(merged)-1][1], interval[1]) 18 } 19 } 20 return merged 21} 22 23func max(x, y int) int { 24 if x > y { 25 return x 26 } 27 return y 28}
In the code above, the max
function is a helper function to determine the maximum of two integers.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.