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

56 - Merge Intervals

Question

Algorithm

Note

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Note

Code

All Problems

All Solutions