DSA sheet / Sorting and searching
Restaurant Customers
Do these first: Distinct Numbers
The problem in brief
You get n customers (up to 200 000), each with an arrival time and a leaving time (up to 10^9). Print the maximum number of customers present at the same moment.
An adapted, shortened summary (changed from the original) shared under the same licence, not a substitute for the statement. The problem is from the CSES Problem Set (Antti Laaksonen), CC BY-NC-SA 4.0. Read the official statement and submit at cses.fi/problemset/task/1619.
Try it
Tab indents; press Esc, then Tab, to leave the box. Ctrl+Enter runs.
Output
Errors
Hints
Stuck? Reveal one hint at a time. Each nudges without giving away the next.
-
Times go up to a billion, so you cannot make an array indexed by time. Which moments could possibly be the busiest?
-
The head count only changes at arrivals and departures. Turn every customer into two events.
-
Sort the events by time and sweep through them, maintaining a running count. Where do you record the maximum?
-
What should happen when one customer leaves at the exact moment another arrives: is the restaurant momentarily fuller or not? Decide the tie rule and put it in the sort order.
The walkthrough
Spoilers ahead: open a section only after you have given the hints a fair try.
How to think
The brute force checks, for every interval, how many others overlap it: O(n^2). The insight that beats it is that a snapshot of “how many people are here” is a step function that only changes at event times. So instead of intervals, think of a stream of +1 and -1 events. The peak of the step function is the answer, and finding the peak of a step function is just a running sum over sorted events.
This is the sweep-line technique: convert objects with extent into point events, sort, and maintain state as you sweep. It generalises to overlapping rectangles, meeting rooms and skyline problems. The habit: when a question is about “at the same time”, ask which finite set of moments can matter, and sweep over exactly those.
Intuition
Stand at the door with a clicker. Every arrival is a click up, every departure a click down. Read out the events in time order; the highest number the clicker ever shows is the answer.
Approach
- For each customer create two events: (arrival, +1) and (leaving, -1).
- Sort all events by time; on equal times put the -1 before the +1 (treat the interval as ending just before its leaving time, so a leaver and an arriver at the same instant do not overlap).
- Sweep: add each event’s delta to a counter and keep the maximum.
- Print the maximum.
The tie rule is the one place a correct-looking sweep can be off by one: this solution treats a leaver and an arriver at the same instant as not overlapping. Pitfalls: 2n events, up to 400 000 items to sort; times fit in 32 bits, and the counter never exceeds n.
Complexity
O(n log n) for the sort, O(n) for the sweep; O(n) memory.
Solutions
Written from scratch and checked by compiling and running each one against a brute force on random inputs. Fast input/output, the way you would submit it.
Show solutions (C++17, Python 3, Java 17, Node.js)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<pair<int, int>> ev;
ev.reserve(2 * n);
for (int i = 0; i < n; i++) {
int a, b;
cin >> a >> b;
ev.push_back({a, +1});
ev.push_back({b, -1}); // (t, -1) sorts before (t, +1): leavers go first on ties
}
sort(ev.begin(), ev.end());
int cur = 0, best = 0;
for (auto &e : ev) {
cur += e.second;
best = max(best, cur);
}
cout << best << "\n";
return 0;
}import sys
def main():
data = sys.stdin.read().split()
n = int(data[0])
events = []
for i in range(n):
events.append((int(data[1 + 2 * i]), 1))
events.append((int(data[2 + 2 * i]), -1))
events.sort() # (t, -1) sorts before (t, 1): leavers go first on ties
cur = best = 0
for _, d in events:
cur += d
if cur > best:
best = cur
print(best)
main()import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
StreamTokenizer st = new StreamTokenizer(new BufferedInputStream(System.in));
st.nextToken();
int n = (int) st.nval;
long[] ev = new long[2 * n];
for (int i = 0; i < n; i++) {
st.nextToken();
long a = (long) st.nval;
st.nextToken();
long b = (long) st.nval;
ev[2 * i] = a * 2 + 1; // arrival: low bit 1
ev[2 * i + 1] = b * 2; // leaving: low bit 0, so it sorts first on ties
}
Arrays.sort(ev);
int cur = 0, best = 0;
for (long e : ev) {
cur += (e & 1) == 1 ? 1 : -1;
best = Math.max(best, cur);
}
System.out.println(best);
}
}const data = require('fs').readFileSync(0, 'utf8').split(/\s+/).filter(Boolean).map(Number);
const n = data[0];
// Encode each event as time * 2 + (1 for arrival, 0 for leaving): leavers sort first on ties.
// Times stay below 2^30, so the encoding is exact in a double.
const ev = new Float64Array(2 * n);
for (let i = 0; i < n; i++) {
ev[2 * i] = data[1 + 2 * i] * 2 + 1;
ev[2 * i + 1] = data[2 + 2 * i] * 2;
}
ev.sort();
let cur = 0;
let best = 0;
for (const e of ev) {
cur += e % 2 === 1 ? 1 : -1;
if (cur > best) best = cur;
}
console.log(best);Problem: CSES Problem Set (Antti Laaksonen, University of Helsinki), CC BY-NC-SA 4.0. The explanations and code above are original (© Anupam Kumar).