Grade 12 · Data structures and the STLCitește în română

pair: union of intervals

Original: pair — reuniunea intervalelor

O(n log n)C++1759 lines1 example

The idea

pair<int, int> groups two values (first, second) and compares lexicographically: first by first, then by second. So sort on an array of pairs orders the intervals by their left end. Then we walk them once: if the current interval starts before the end of the one being built (or exactly there), we merge it, extending the end; otherwise we close the interval being built and start a new one. The program prints the intervals of the union, from left to right.

Original description (Romanian)

pair<int, int> grupează două valori (first, second) și se compară lexicografic: întâi după first, apoi după second. Așadar sort pe un vector de perechi ordonează intervalele după capătul stâng. Apoi le parcurgem o dată: dacă intervalul curent începe înainte de sfârșitul celui în construcție (sau chiar acolo), îl lipim, prelungind sfârșitul; altfel închidem intervalul construit și începem altul. Programul afișează intervalele reuniunii, de la stânga la dreapta.

Complexity
O(n log n)
Grade
Grade 12 (Clasa a XII-a)

Examples

Example 1

Input

5
1 3
8 10
2 6
15 18
10 12

Expected output

1 6
8 12
15 18

The code

Comments are in Romanian, as in the original collection. Edit freely: you can reset at any time.

pair-reuniunea-intervalelor.cpp
/*
 * Titlu: pair — reuniunea intervalelor
 * Clasa: 12
 * Capitol: Structuri de date și STL
 * Descriere: pair<int, int> grupează două valori (first, second) și se compară
 *            lexicografic: întâi după first, apoi după second. Așadar sort pe un
 *            vector de perechi ordonează intervalele după capătul stâng. Apoi le
 *            parcurgem o dată: dacă intervalul curent începe înainte de sfârșitul
 *            celui în construcție (sau chiar acolo), îl lipim, prelungind
 *            sfârșitul; altfel închidem intervalul construit și începem altul.
 *            Programul afișează intervalele reuniunii, de la stânga la dreapta.
 * Complexitate: O(n log n)
 *
 * Exemplu
 * Intrare:
 * 5
 * 1 3
 * 8 10
 * 2 6
 * 15 18
 * 10 12
 * Ieșire:
 * 1 6
 * 8 12
 * 15 18
 */
#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<pair<int, int>> v(n);
    for (int i = 0; i < n; i++)
        cin >> v[i].first >> v[i].second;
    sort(v.begin(), v.end());

    vector<pair<int, int>> reuniune;
    pair<int, int> curent = v[0];
    for (int i = 1; i < n; i++)
    {
        if (v[i].first <= curent.second)
            curent.second = max(curent.second, v[i].second);
        else
        {
            reuniune.push_back(curent);
            curent = v[i];
        }
    }
    reuniune.push_back(curent);
    for (auto &p : reuniune)
        cout << p.first << ' ' << p.second << '\n';
    return 0;
}

Runs on a real g++ (C++17, -O2) through Compiler Explorer. Keep runs short; there's a time limit.