Practice › Greedy
Insert Interval
Medium · Greedy · Asked at Google, Amazon, Meta, LinkedIn
The intervals are sorted by start and do not overlap. Insert the new interval and merge where necessary (intervals that touch, like [1,3] and [3,5], are merged). Print the resulting intervals.
Input
First line: n. Next n lines: start end. Last line: the new interval start end.
Output
The intervals after insertion, one start end per line.
Constraints
- 0 ≤ n ≤ 10^5
- 0 ≤ start ≤ end ≤ 10^9
Three phases: copy the intervals that end before the new one starts, merge all that overlap it, then copy the rest.
Example 1
Input
2 1 3 6 9 2 5
Output
1 5 6 9
Example 2
Input
5 1 2 3 5 6 7 8 10 12 16 4 8
Output
1 2 3 10 12 16
Hints
- The input is already sorted and non-overlapping, so no sorting is needed.
- Copy intervals that end before the new one starts; merge every interval that overlaps (or touches) it; copy the rest.
Approach
Phase 1: while iv[i].end < newStart, output iv[i] unchanged. Phase 2: while iv[i].start ≤ newEnd, the interval overlaps or touches — widen the new interval to [min(start), max(end)]. Output the merged new interval. Phase 3: output the remaining intervals. One linear pass.
Complexity: O(n) time · O(n) space for the output
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<pair<long long, long long>> iv(n);
for (auto &x : iv) cin >> x.first >> x.second;
long long a, b;
cin >> a >> b;
vector<pair<long long, long long>> out;
int i = 0;
while (i < n && iv[i].second < a) out.push_back(iv[i++]);
while (i < n && iv[i].first <= b) {
a = min(a, iv[i].first);
b = max(b, iv[i].second);
i++;
}
out.push_back({a, b});
while (i < n) out.push_back(iv[i++]);
for (auto &x : out) cout << x.first << " " << x.second << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
n = data[0]
iv = [(data[1 + 2 * i], data[2 + 2 * i]) for i in range(n)]
a, b = data[1 + 2 * n], data[2 + 2 * n]
out, i = [], 0
while i < n and iv[i][1] < a:
out.append(iv[i])
i += 1
while i < n and iv[i][0] <= b:
a, b = min(a, iv[i][0]), max(b, iv[i][1])
i += 1
out.append((a, b))
out += iv[i:]
print("\n".join(f"{x} {y}" for x, y in out))Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long[][] iv = new long[n][2];
for (int i = 0; i < n; i++) {
iv[i][0] = sc.nextLong();
iv[i][1] = sc.nextLong();
}
long a = sc.nextLong(), b = sc.nextLong();
StringBuilder sb = new StringBuilder();
int i = 0;
while (i < n && iv[i][1] < a) { sb.append(iv[i][0]).append(' ').append(iv[i][1]).append('\n'); i++; }
while (i < n && iv[i][0] <= b) {
a = Math.min(a, iv[i][0]);
b = Math.max(b, iv[i][1]);
i++;
}
sb.append(a).append(' ').append(b).append('\n');
while (i < n) { sb.append(iv[i][0]).append(' ').append(iv[i][1]).append('\n'); i++; }
System.out.print(sb);
}
}