The Sweep Line Method

Lesson 4 of 7 · Advanced techniques

Imagine a vertical line that moves over the number line from left to right and stops only at the interesting places – the events: the beginnings and the ends of intervals. Instead of checking every point, we sort the events and process them in order. This is how tasks with intervals, schedules and overlaps are solved.

Before you start: prior knowledge you need – the sort function (SR), prefix sums.
How to learn: retype and run every example, and solve the tasks at the end on your own first; open the hint and the solution only after that. All programs are in C++.

The most intervals at the same time

A museum had n visitors; for each of them we know the arrival time a and the departure time b. What is the largest number of people that were there at the same time? Every visitor gives two events: (a, +1) and (b, −1). We sort the events by time and go through them, changing a counter.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<pair<int, int>> events;             // (time, change)
    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        events.push_back({a, +1});             // arrival
        events.push_back({b, -1});             // departure
    }
    sort(events.begin(), events.end());        // at the same time -1 comes before +1
    int current = 0, best = 0;
    for (auto &e : events) {
        current += e.second;
        best = max(best, current);
    }
    cout << best << endl;
    return 0;
}

For the visitors 1 4, 2 6, 4 8, 5 7 the program prints 3 (at time 5 the second, third and fourth visitors are there).

The pairs are sorted by time, and with equal times by the second value: −1 before +1. This means that a visitor who leaves at time 4 and one who arrives at time 4 are not in the museum at the same time. If the task says they count as being there at the same time, the departure is encoded with the time b + 1, or the order is changed.

The total covered length

n segments [a, b] are drawn on a line. What is the total length covered by at least one segment? While sweeping we remember how many segments currently cover the line; the part between two consecutive events is counted if the counter is greater than 0.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<pair<long long, int>> events;
    for (int i = 0; i < n; i++) {
        long long a, b;
        cin >> a >> b;
        events.push_back({a, +1});
        events.push_back({b, -1});
    }
    sort(events.begin(), events.end());
    long long total = 0;
    int active = 0;
    for (size_t i = 0; i < events.size(); i++) {
        if (i > 0 && active > 0) total += events[i].first - events[i - 1].first;   // the part since the previous event
        active += events[i].second;
    }
    cout << total << endl;
    return 0;
}

The segments [1, 4] and [2, 6] together cover [1, 6] (length 5), and [8, 10] another 2 – 7 in total; for this input the program prints 7. Merging intervals (SR) gives the same result.

The connection with the difference array

When the times are small integers (up to 106), instead of sorting the events we can use a difference array: d[a]++, d[b]--, and the prefix sum then gives the number of active intervals at every point. The sweep line method also works when the times are large (up to 109) or real – that is why it is more general.

Practice tasks

Every task has an example, a hint and a solution. The solutions have been checked on the examples in the text.

TASK 01Difficulty: medium

The number of rooms needed

For n lectures we are given the start and end times [s, e) (a lecture that ends at 10 and one that starts at 10 can be in the same room). What is the smallest number of rooms needed?

Example 1

Input

3
0 30
5 10
15 20

Output

2

Example 2

Input

2
1 10
10 20

Output

1
TASK 02Difficulty: medium

The longest period without visitors

A museum is open from time 0 to T. We are given the intervals during which n visitors stayed. How long is the longest uninterrupted period in which nobody was in the museum?

Example 1

Input

10 2
2 4
3 6

Output

4

Example 2

Input

5 1
0 5

Output

0
Common mistakes and tips
  • Decide carefully on the order of events at the same moment (an end before a start or the other way round) – it depends on the task.
  • Store the events as pairs and sort them; do not go through all possible times if they go up to 109.
  • The counter of active intervals must never be negative – if it is, the order of the events is wrong.

Check your knowledge

Open the quiz

The sweep line method

1. How many events does one interval [a, b] give?




2. What is the complexity of the sweep line method for n intervals?




3. The smallest number of rooms for lectures is equal to…