Getting everything ready for you…

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

0s

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

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

  1. Sort the intervals by their start.
  2. 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);
    }
}

Solve Merge Intervals online · All practice problems