Problem Statement:
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.
Example 3:
Input: intervals = [[4,7],[1,4]]
Output: [[1,7]]
Explanation: Intervals [1,4] and [4,7] are considered overlapping.
Constraints
1 <= intervals.length <= 104intervals[i].length == 20 <= starti <= endi<= 105
Approach:
- Sort intervals by their starting point.
- Initialize
result with the first interval. - Traverse
intervalsone by one:- If the current interval overlaps with the last interval in the result → merge them (update the end to the max end).
- Otherwise →
addit as a new interval.
- Return the merged list.
Time & Space Complexity:
Time Complexity: O(n log n)
Space Complexity: O(n)
Dry Run
Input: arr = [[2,5],[1,3],[6,9]]
Step 0: Start Function: merge(arr) arr = [[2,5], [1,3], [6,9]] n = arr.length = 3 (no ans yet) Step 1: Sort intervals by start → arr.sort((a,b) => a[0]-b[0]) Before sort: [[2,5], [1,3], [6,9]] After sort: [[1,3], [2,5], [6,9]] Step 2: Initialize answer array ans = [arr[0]] = [[1,3]] Step 3: Loop through remaining intervals (for i = 1 → 2) Iteration (i = 1): - current = arr[1] = [2,5] - last in ans = ans[ans.length-1] = [1,3] - Check overlap: current[0] <= last[1] → 2 <= 3 ? → true (overlap) - Merge: last[1] = max(last[1], current[1]) = max(3,5) = 5 - ans becomes [[1,5]] - (do not push new interval) Iteration (i = 2): - current = arr[2] = [6,9] - last in ans = [1,5] - Check overlap: 6 <= 5 ? → false (no overlap) - Push current into ans → ans = [[1,5], [6,9]] Step 4: End loop Final ans = [[1,5], [6,9]] Explanation: Sorting produced [[1,3],[2,5],[6,9]]. [1,3] and [2,5] overlapped and merged into [1,5]. [6,9] did not overlap, so it was appended unchanged.
Output: [[1,5],[6,9]]
var merge = function(arr) {
arr.sort((a, b) => (a[0] - b[0]));
let ans = [arr[0]];
for(let i = 1; i < arr.length; i++){
if(arr[i][0] <= ans[ans.length - 1][1]){
ans[ans.length-1][1] = Math.max(ans[ans.length-1][1], arr[i][1])
} else {
ans.push(arr[i]);
}
}
return ans;
};
from typing import List
def merge(intervals: List[List[int]]) -> List[List[int]]:
if not intervals:
return []
intervals.sort(key=lambda x: x[0])
ans = [intervals[0]]
for i in range(1, len(intervals)):
if intervals[i][0] <= ans[-1][1]:
ans[-1][1] = max(ans[-1][1], intervals[i][1])
else:
ans.append(intervals[i])
return ans
import java.util.*;
public class Solution {
public int[][] merge(int[][] intervals) {
if (intervals == null || intervals.length == 0) return new int[0][];
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
List ans = new ArrayList<>();
ans.add(new int[]{intervals[0][0], intervals[0][1]});
for (int i = 1; i < intervals.length; i++) {
int[] last = ans.get(ans.size() - 1);
if (intervals[i][0] <= last[1]) {
last[1] = Math.max(last[1], intervals[i][1]);
} else {
ans.add(new int[]{intervals[i][0], intervals[i][1]});
}
}
return ans.toArray(new int[ans.size()][]);
}
}
#include <bits/stdc++.h>
using namespace std;
vector> mergeIntervals(vector>& intervals) {
if (intervals.empty()) return {};
sort(intervals.begin(), intervals.end(), [](const vector& a, const vector& b){
return a[0] < b[0];
});
vector> ans;
ans.push_back(intervals[0]);
for (size_t i = 1; i < intervals.size(); ++i) {
if (intervals[i][0] <= ans.back()[1]) {
ans.back()[1] = max(ans.back()[1], intervals[i][1]);
} else {
ans.push_back(intervals[i]);
}
}
return ans;
}
#include <stdlib.h>
#include <stdio.h>
typedef struct {
int start;
int end;
} Interval;
int cmp(const void* a, const void* b) {
Interval *ia = (Interval*)a;
Interval *ib = (Interval*)b;
return ia->start - ib->start;
}
Interval* mergeIntervals(Interval* intervals, int intervalsSize, int* outSize) {
*outSize = 0;
if (intervalsSize == 0) return NULL;
Interval* arr = malloc(sizeof(Interval) * intervalsSize);
for (int i = 0; i < intervalsSize; ++i) arr[i] = intervals[i];
qsort(arr, intervalsSize, sizeof(Interval), cmp);
Interval* result = malloc(sizeof(Interval) * intervalsSize);
int ri = 0;
result[0] = arr[0];
ri = 1;
for (int i = 1; i < intervalsSize; ++i) {
if (arr[i].start <= result[ri-1].end) {
if (arr[i].end > result[ri-1].end)
result[ri-1].end = arr[i].end;
} else {
result[ri++] = arr[i];
}
}
free(arr);
*outSize = ri;
return result;
}
using System;
using System.Collections.Generic;
public class Solution {
public IList Merge(int[][] intervals) {
var res = new List();
if (intervals == null || intervals.Length == 0) return res;
Array.Sort(intervals, (a, b) => a[0].CompareTo(b[0]));
res.Add(new int[] { intervals[0][0], intervals[0][1] });
for (int i = 1; i < intervals.Length; i++) {
int[] last = res[res.Count - 1];
if (intervals[i][0] <= last[1]) {
last[1] = Math.Max(last[1], intervals[i][1]);
} else {
res.Add(new int[] { intervals[i][0], intervals[i][1] });
}
}
return res;
}
}
