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
Hint
The smallest number of rooms is equal to the largest number of lectures that take place at the same moment – the sweep line method. At the same moment an end (−1) is processed before a start (+1).
Solution (C++)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
vector<pair<int, int>> events;
for (int i = 0; i < n; i++) {
int s, e;
cin >> s >> e;
events.push_back({s, +1});
events.push_back({e, -1});
}
sort(events.begin(), events.end()); // (t, -1) before (t, +1)
int current = 0, best = 0;
for (auto &ev : events) {
current += ev.second;
best = max(best, current);
}
cout << best << endl;
return 0;
}
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
Hint
Go through the events and remember the moment when the number of people present dropped to 0. When someone arrives while the museum is empty, the length of the empty period is the difference. Do not forget the period from 0 to the first arrival and from the last departure to T.
Solution (C++)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
long long T;
int n;
cin >> T >> 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 emptySince = 0, best = 0; // the museum is empty from time 0
int current = 0;
for (auto &e : events) {
if (current == 0 && e.second == +1) best = max(best, e.first - emptySince); // the end of an empty period
current += e.second;
if (current == 0) emptySince = e.first; // the start of an empty period
}
best = max(best, T - emptySince); // from the last departure until closing
cout << best << endl;
return 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…
Podešavanja kolačića
Koristimo kolačiće da bismo vam pružili najbolje moguće iskustvo. Takođe nam omogućavaju da analiziramo ponašanje korisnika kako bismo stalno poboljšavali veb lokaciju za vas.