Algorithm


Problem Name: 56. Merge Intervals

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

Code Examples

#1 Code Example with C Programming

Code - C Programming


int cmp(const void *a, const void *b) {
    return (*(struct Interval *)a).start - (*(struct Interval *)b).start;
}
struct Interval* merge(struct Interval* intervals, int intervalsSize, int* returnSize) {
    int i, j;

    if (intervalsSize  < = 0) return NULL;

    qsort(intervals, intervalsSize, sizeof(struct Interval), cmp);

    i = 0;
    for (j = 1; j  <  intervalsSize; j ++) {
        if (intervals[j].start > intervals[i].end) {
            // append
            intervals[++ i] = intervals[j];
        } else if (intervals[j].end > intervals[i].end) {
            // merge
            intervals[i].end = intervals[j].end;
        }   // ignore it
    }

    *returnSize = i + 1;

    return intervals;
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
intervals = [[1,3],[2,6],[8,10],[15,18]]

Output

x
+
cmd
[[1,6],[8,10],[15,18]]

#2 Code Example with C++ Programming

Code - C++ Programming


class Solution {
public:
    vector<Interval> merge(vector<Interval>& intervals) {
        sort(intervals.begin(), intervals.end(), [](Interval& a, Interval& b){ return a.start < b.start; });
        vector < Interval>res;
        for(int i = 0; i  <  intervals.size(); i++)
            if(res.empty() || res.back().end < intervals[i].start) res.push_back(intervals[i]);
            else res.back().end = max(res.back().end, intervals[i].end>;
        return res;
    }
};
Copy The Code & Try With Live Editor

Input

x
+
cmd
intervals = [[1,4],[4,5]]

Output

x
+
cmd
[[1,5]]

#3 Code Example with Java Programming

Code - Java Programming


class Solution {
  public int[][] merge(int[][] intervals) {
    Arrays.sort(intervals, Comparator.comparingInt((int[] o) -> o[0]).thenComparingInt(o -> o[1]));
    List < int[]> mergedIntervals = new ArrayList<>();
    int idx = 0;
    while (idx  <  intervals.length) {
      int currentStart = intervals[idx][0];
      int currentEnd = intervals[idx][1];
      idx++;
      while (idx  <  intervals.length && intervals[idx][0] <= currentEnd) {
        currentEnd = Math.max(intervals[idx][1], currentEnd);
        idx++;
      }
      mergedIntervals.add(new int[]{currentStart, currentEnd});
    }
    int[][] result = new int[mergedIntervals.size()][2];
    for (int i = 0; i  <  mergedIntervals.size(); i++) {
      result[i] = mergedIntervals.get(i);
    }
    return result;
  }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
intervals = [[1,3],[2,6],[8,10],[15,18]]

Output

x
+
cmd
[[1,6],[8,10],[15,18]]

#4 Code Example with Javascript Programming

Code - Javascript Programming


const merge = function(intervals) {
  intervals.sort((a, b) => a[0] - b[0] || a[1] - b[1])
  const res = [intervals[0]]
  for(let i = 1, n = intervals.length; i  <  n; i++) {
    const [s, e] = intervals[i]
    const pre = res[res.length - 1]
    if(s <= pre[1]) {
      pre[1] = Math.max(pre[1], e)
    } else {
      res.push(intervals[i]>
    }
  }
  return res
};

Copy The Code & Try With Live Editor

Input

x
+
cmd
intervals = [[1,3],[2,6],[8,10],[15,18]]

Output

x
+
cmd
[[1,6],[8,10],[15,18]]

#5 Code Example with Python Programming

Code - Python Programming


class Solution:
    def merge(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: List[Interval]
        """
        res = []
        intervals.sort(key = lambda x: x.end)
        for intr in intervals:
            if not re:
                res.append([intr.start, intr.end])
            else:
                s = intr.start
                while res and res[-1][1] >= intr.start:
                    s = min(s, res.pop()[0])
                res.append([s, intr.end])
        return res
Copy The Code & Try With Live Editor

Input

x
+
cmd
intervals = [[1,3],[2,6],[8,10],[15,18]]

Output

x
+
cmd
[[1,6],[8,10],[15,18]]

#6 Code Example with C# Programming

Code - C# Programming


using System;
using System.Collections.Generic;
using System.Linq;

namespace LeetCode
{
    public class _056_MergeIntervals
    {
        public int[][] Merge(int[][] intervals)
        {
            if (intervals.Length  < = 1) return intervals;

            Array.Sort(intervals, (a, b) =>
            {
                var comp = a[0].CompareTo(b[0]);
                if (comp == 0)
                    comp = a[1].CompareTo(b[1]);
                return comp;
            });

            var result = new List < int[]>();
            result.Add(intervals[0]);
            for (int i = 1; i  <  intervals.Length; i++)
            {
                if (result.Last()[1] >= intervals[i][0])
                {
                    if (result.Last()[1] < intervals[i][1])
                        result.Last()[1] = intervals[i][1];
                }
                else
                    result.Add(intervals[i]);
            }

            return result.ToArray(); ;
        }
    }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
intervals = [[1,3],[2,6],[8,10],[15,18]]

Output

x
+
cmd
[[1,6],[8,10],[15,18]]
Advertisements

Demonstration


Previous
#55 Leetcode - Jump Game Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#57 Leetcode - Insert Interval Solution in C, C++, Java, JavaScript, Python, C# Leetcode