Practice › Arrays
Merge Intervals
Medium · Arrays · Asked at Google, Amazon, Microsoft, Uber, Flipkart
Merge all overlapping intervals. Two intervals overlap if they share at least one point (so [1,4] and [4,5] merge into [1,5]).
Input
First line: n. Next n lines: start end.
Output
The merged intervals sorted by start, one start end per line.
Constraints
- 1 ≤ n ≤ 10^4
- 0 ≤ start ≤ end ≤ 10^4
Sort by start, then extend the last merged interval or start a new one.
Example 1
Input
4 1 3 2 6 8 10 15 18
Output
1 6 8 10 15 18
Example 2
Input
2 1 4 4 5
Output
1 5
Hints
- Sort the intervals by their start.
- Then each interval either overlaps the last merged one (start ≤ last end) or starts a new group.
Approach
After sorting by start, overlapping intervals are next to each other. Keep a list of merged intervals. For each interval, if its start is ≤ the end of the last merged interval, extend that end to max(end, lastEnd). Otherwise append it as a new interval. Using ≤ (not <) makes touching intervals such as [1,4] and [4,5] merge.
Complexity: O(n log n) time · O(n) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<pair<int, int>> iv(n);
for (auto &p : iv) cin >> p.first >> p.second;
sort(iv.begin(), iv.end());
vector<pair<int, int>> merged;
for (auto &p : iv) {
if (!merged.empty() && p.first <= merged.back().second)
merged.back().second = max(merged.back().second, p.second);
else
merged.push_back(p);
}
for (auto &p : merged) cout << p.first << " " << p.second << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
n = data[0]
iv = sorted((data[1 + 2 * i], data[2 + 2 * i]) for i in range(n))
merged = []
for s, e in iv:
if merged and s <= merged[-1][1]:
merged[-1][1] = max(merged[-1][1], e)
else:
merged.append([s, e])
print("\n".join(f"{s} {e}" for s, e in merged))Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[][] iv = new int[n][2];
for (int i = 0; i < n; i++) {
iv[i][0] = sc.nextInt();
iv[i][1] = sc.nextInt();
}
Arrays.sort(iv, (x, y) -> x[0] != y[0] ? Integer.compare(x[0], y[0]) : Integer.compare(x[1], y[1]));
List<int[]> merged = new ArrayList<>();
for (int[] p : iv) {
if (!merged.isEmpty() && p[0] <= merged.get(merged.size() - 1)[1]) {
int[] last = merged.get(merged.size() - 1);
last[1] = Math.max(last[1], p[1]);
} else {
merged.add(new int[] { p[0], p[1] });
}
}
StringBuilder sb = new StringBuilder();
for (int[] p : merged) sb.append(p[0]).append(' ').append(p[1]).append('\n');
System.out.print(sb);
}
}