Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/56.html
56 Merge Intervals
Given a collection of intervals, merge all overlapping intervals.
For example,
Given [1,3],[2,6],[8,10],[15,18]
,
return [1,6],[8,10],[15,18]
.
Algorithm
The first thing to do is to sort
the interval set. Since what we want to sort is a structure, we have to define our own comparator before we can use sort to sort. We sort by the value of start from small to large.
After sorting, we can start to merge, first save the first interval in the result, and then traverse the interval set from the second.
- If the last interval in the result does not overlap with the current interval traversed, the current interval is directly stored in the result,
- if there is overlap, update the end value of the last interval in the result to the larger of the end value of the last interval in the result and the current end value, and then continue to traverse the interval set, and so on to get the final result.
Note
If merge then do not join the list, if there is no merge then add (i,j)
and then update i,j
.
The last interval is outside the for, if you want to check, it may be missed.
Code
Java
-
import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class Merge_Intervals { /** * Definition for an interval. * public class Interval { * int start; * int end; * Interval() { start = 0; end = 0; } * Interval(int s, int e) { start = s; end = e; } * } */ class Solution_optimize { public int[][] merge(int[][] intervals) { if (intervals == null || intervals.length == 0) { return intervals; } Arrays.sort(intervals, (a, b) -> a[0] - b[0]); List<int[]> result = new ArrayList<>(); for (int[] each: intervals) { if (result.isEmpty() || result.get(result.size() - 1)[1] < each[0]) { result.add(each); } else { result.get(result.size() - 1)[1] = Math.max(result.get(result.size() - 1)[1], each[1]); } } int[][] merged = new int[result.size()][]; for (int i = 0; i < result.size(); i++) { merged[i] = result.get(i); } return merged; } } class Solution { public int[][] merge(int[][] intervals) { if (intervals == null || intervals.length == 0) { return intervals; } Arrays.sort(intervals, (a, b) -> a[0] - b[0]); List<int[]> result = new ArrayList<>(); int[] prev = intervals[0]; for (int i = 1; i < intervals.length; i++) { int[] current = intervals[i]; if (prev[1] < current[0] || prev[0] > current[1]) { // no overlap result.add(prev); prev = current; } else { prev[0] = Math.min(prev[0], current[0]); prev[1] = Math.max(prev[1], current[1]); } } // @note: must have, final check result.add(prev); // last node int[][] merged = new int[result.size()][]; for (int i = 0; i < result.size(); i++) { merged[i] = result.get(i); } return merged; } } }
-
// OJ: https://leetcode.com/problems/merge-intervals/ // Time: O(NlogN) // Space: O(1) class Solution { public: vector<vector<int>> merge(vector<vector<int>>& A) { sort(begin(A), end(A)); vector<vector<int>> ans; for (auto &v : A) { if (ans.empty() || v[0] > ans.back()[1]) ans.push_back(v); else ans.back()[1] = max(ans.back()[1], v[1]); } return ans; } };
-
# Definition for an interval. # class Interval(object): # def __init__(self, s=0, e=0): # self.start = s # self.end = e class Solution(object): def merge(self, intervals): """ :type intervals: List[Interval] :rtype: List[Interval] """ ans = [] for intv in sorted(intervals, key=lambda x: x.start): if ans and ans[-1].end >= intv.start: ans[-1].end = max(ans[-1].end, intv.end) else: ans.append(intv) return ans # python3 class Solution: def merge(self, intervals: List[List[int]]) -> List[List[int]]: result = [] intervals.sort(key=lambda x: x[0]) for ind, intv in enumerate(intervals): if not result: result.append(intv) else: if result[-1][1] < intv[0]: result.append(intv) else: result[-1][1] = max(result[-1][1], intv[1]) return result ############ class Solution: def merge(self, intervals: List[List[int]]) -> List[List[int]]: intervals.sort() ans = [] st, ed = intervals[0] for s, e in intervals[1:]: if ed < s: ans.append([st, ed]) st, ed = s, e else: ed = max(ed, e) ans.append([st, ed]) return ans