Question

Formatted question description: https://leetcode.ca/all/56.html

Given an array of intervals where intervals[i] = [start_i, end_i], 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 <= 10⁴
intervals[i].length == 2
0 <= start_i <= end_i <= 10⁴

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
    }
}

56 - Merge Intervals

Question

Algorithm

Note

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Note

Code

All Problems

All Solutions