Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. The input is already sorted and non-overlapping, so no sorting is needed.
  2. 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);
    }
}

Solve Insert Interval online · All practice problems