Sorting and Events
Turn interval and query problems into a left-to-right sweep over sorted add, remove, and inspect events.
Sorting and Events
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
Many contest problems are not fundamentally about geometry or fancy data structures. They are about noticing that all important changes happen at a finite set of coordinates. Once those coordinates are sorted, the problem becomes a sweep over events.
When to Use It
This pattern is a good fit when:
intervals start and end,
queries ask ``what is active at coordinate \(x\)?'',
the answer only changes when the sweep line crosses an endpoint, a query point, or another special coordinate.
It is one of the cleanest ways to reduce \(O(nq)\) scans into \(O((n+q)\log(n+q))\) offline processing.
Core Idea
Encode each structural change as an event:
add an interval,
remove an interval,
answer a query.
Sort all events by coordinate, decide a tie-breaking order, and maintain the active state while sweeping from left to right.
Key Insight
The real invariant is not ``where the sweep line is.'' It is ``which objects intersect the current position.'' If that active set can be updated locally when crossing one event, then the entire problem becomes a sequence of small changes instead of repeated full recomputation.
Worked Problem
Problem.
You are given closed intervals \([l_i, r_i]\) and query points \(x_j\). For each query, count how many intervals contain it.
Why events fit.
An interval contributes \(+1\) starting at \(l_i\) and stops contributing after \(r_i\). A query only needs the number of intervals that are active exactly at its coordinate.
Algorithm outline.
Create events \((l_i, \texttt{add})\), \((r_i, \texttt{remove})\), and \((x_j, \texttt{query})\).
Sort by coordinate.
For equal coordinates, process
addbeforequerybeforeremovefor closed intervals.Maintain one integer
active.
Problem Pattern
This exact structure also appears in:
maximum overlap of intervals,
offline stabbing queries,
rectangle union and line sweeps, after the state becomes richer than one counter,
counting how many resources are currently occupied.
Correctness Intuition
Between two consecutive event coordinates, the active set does not change. So it is enough to update the state only at events. The tie-breaking rule is the only place where the interval semantics matter: closed, open, and half-open intervals need different ordering.
Complexity Analysis
If there are \(E\) total events, sorting costs \(O(E \log E)\) and the sweep is linear after sorting.
Implementation
The sample code solves the interval stabbing problem above. The same event representation extends naturally when the active state becomes a Fenwick tree, multiset, or segment tree instead of one integer.
Common Pitfalls
Getting tie-breaking wrong at equal coordinates.
Mixing closed-interval logic with half-open implementation.
Forgetting that offline event sorting loses the original query order unless IDs are stored.
Using an event sweep when the hard part is really a graph interaction, not a one-dimensional ordering.
Variants / Extensions
Coordinate compression before the sweep.
Two-dimensional sweep line with an auxiliary data structure.
Difference-array interpretation when events only change one counter.
Practice Problems
Count interval coverage at query points.
Find the maximum number of simultaneously active segments.
Offline process add/remove/query actions sorted by one key.
References
Code
Contest-ready reference implementation for the idea explained above.
struct Event {
long long x;
int type; // 0 = add, 1 = query, 2 = remove
int id;
};
vector<int> count_covering_intervals(
const vector<pair<long long, long long>>& intervals,
const vector<long long>& queries
) {
vector<Event> events;
events.reserve(intervals.size() * 2 + queries.size());
for (auto [l, r] : intervals) {
events.push_back({l, 0, -1});
events.push_back({r, 2, -1});
}
for (int i = 0; i < (int)queries.size(); ++i) {
events.push_back({queries[i], 1, i});
}
sort(events.begin(), events.end(), [](const Event& a, const Event& b) {
if (a.x != b.x) return a.x < b.x;
return a.type < b.type;
});
int active = 0;
vector<int> answer(queries.size());
for (const Event& event : events) {
if (event.type == 0) {
++active;
} else if (event.type == 1) {
answer[event.id] = active;
} else {
--active;
}
}
return answer;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.