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 <= 104intervals[i].length == 20 <= 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;
}
Input
intervals = [[1,3],[2,6],[8,10],[15,18]]
Output
[[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;
}
};
Input
intervals = [[1,4],[4,5]]
Output
[[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;
}
}
Input
intervals = [[1,3],[2,6],[8,10],[15,18]]
Output
[[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
};
Input
intervals = [[1,3],[2,6],[8,10],[15,18]]
Output
[[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
Input
intervals = [[1,3],[2,6],[8,10],[15,18]]
Output
[[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(); ;
}
}
}
Input
intervals = [[1,3],[2,6],[8,10],[15,18]]
Output
[[1,6],[8,10],[15,18]]