Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/56.html
Given an array of intervals
where intervals[i] = [starti, endi]
, merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.
Example 1:
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].
Example 2:
Input: intervals = [[1,4],[4,5]] Output: [[1,5]] Explanation: Intervals [1,4] and [4,5] are considered overlapping.
Constraints:
1 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 104
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
-
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; } } } ############ class Solution { public int[][] merge(int[][] intervals) { Arrays.sort(intervals, Comparator.comparingInt(a -> a[0])); int st = intervals[0][0], ed = intervals[0][1]; List<int[]> ans = new ArrayList<>(); for (int i = 1; i < intervals.length; ++i) { int s = intervals[i][0], e = intervals[i][1]; if (ed < s) { ans.add(new int[] {st, ed}); st = s; ed = e; } else { ed = Math.max(ed, e); } } ans.add(new int[] {st, ed}); return ans.toArray(new int[ans.size()][]); } }
-
// 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) or 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
-
func merge(intervals [][]int) [][]int { sort.Slice(intervals, func(i, j int) bool { return intervals[i][0] < intervals[j][0] }) st, ed := intervals[0][0], intervals[0][1] var ans [][]int for _, e := range intervals[1:] { if ed < e[0] { ans = append(ans, []int{st, ed}) st, ed = e[0], e[1] } else if ed < e[1] { ed = e[1] } } ans = append(ans, []int{st, ed}) return ans }
-
function merge(intervals: number[][]): number[][] { intervals.sort((a, b) => a[0] - b[0]); let ans: number[][] = []; let index: number = -1; for (let interval of intervals) { if (index == -1 || ans[index][1] < interval[0]) { // 保留 ans.push(interval); index++; } else { // 求交集 ans[index][1] = Math.max(ans[index][1], interval[1]); } } return ans; }
-
public class Solution { public int[][] Merge(int[][] intervals) { intervals = intervals.OrderBy(a => a[0]).ToArray(); int st = intervals[0][0], ed = intervals[0][1]; var ans = new List<int[]>(); for (int i = 1; i < intervals.Length; ++i) { int s = intervals[i][0], e = intervals[i][1]; if (ed < s) { ans.Add(new int[]{st, ed}); st = s; ed = e; } else { ed = Math.Max(ed, e); } } ans.Add(new int[]{st, ed}); return ans.ToArray(); } }
-
impl Solution { pub fn merge(mut intervals: Vec<Vec<i32>>) -> Vec<Vec<i32>> { intervals.sort_unstable_by(|a, b| a[0].cmp(&b[0])); let n = intervals.len(); let mut res = vec![]; let mut i = 0; while i < n { let l = intervals[i][0]; let mut r = intervals[i][1]; i += 1; while i < n && r >= intervals[i][0] { r = r.max(intervals[i][1]); i += 1; } res.push(vec![l, r]); } res } }