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.