Sweep Line Algorithm — Fundamentals

A sweep line turns a spatial problem into an ordered sequence of events. Instead of reconsidering the whole picture, maintain only the state affected by the current coordinate. We begin with one-dimensional interval union length and maximum overlap, a clean model for later two-dimensional sweeps. The same event/state separation extends to segments and rectangles, but each problem needs its own active-set invariant.

Prerequisites: Sorting, intervals and loop invariants.

Build the idea

1. Choose events and state

   For an interval [l,r), create an entry +1 at l and exit −1 at r. Normalize reversed endpoints and ignore zero-length intervals. Sort all event coordinates. active counts how many intervals cover the open slab between the previous coordinate and the current one. Because no endpoint lies inside that slab, the count cannot change there.

2. Integrate a constant slab

   Before applying events at x, if active>0 add x−previous to union length. This charges the entire gap exactly once regardless of how many intervals overlap. Adding every interval length would overcount overlap. Track the maximum active count after each coordinate group to measure maximum coverage on a positive-length slab.

   $$\mathrm{covered}+=(x-\mathrm{previousX})·[\mathrm{active}>0]$$

3. Batch simultaneous events

   At a shared coordinate, sum all entries and exits before updating active. Their internal order has no effect on lengths, but inspecting a transient count could falsely count touching endpoints as a positive-length overlap. This lesson uses half-open intervals and ignores isolated endpoint-only overlap. Different output semantics require different event ordering.

4. Trace the sample

   For [1,4),[2,6),[6,8), active becomes 1 at x=1 and 2 at x=2. It drops to 1 at 4. At 6, one interval exits and another enters, leaving active=1. The covered slabs total 1+2+2+2=7 and the maximum positive-length overlap is 2. The intervals touching at 6 do not create an additional overlapping region.

5. Generalize cautiously

   In two dimensions the sweep coordinate is often x, while an active structure summarizes y-information. Orthogonal intersections need range counts; rectangle union needs covered y-length. General segment-intersection sweeps need ordered geometry and intersection events, and a mutable comparator can break a balanced tree. Knowing the sweep pattern is not a substitute for proving the specific active-set rules.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
int main(){
    int n;
    std::cin>>n;
    std::vector<std::pair<long long,int>>events;
    for(int i=0;i<n;++i){
        long long l,r;
        std::cin>>l>>r;
        if(l>r){
            std::swap(l,r);
        }
        if(l==r){
            continue;
        }
        events.push_back({l,1});
        events.push_back({r,-1});
    }
    std::sort(events.begin(),events.end());
    long long covered=0,previous=0;
    int active=0,maximum=0;
    for(int i=0;i<(int)events.size();){
        long long x=events[i].first;
        if(active>0){
            covered+=x-previous; // State describes the open slab before this event.
        }
        int delta=0;
        while(i<(int)events.size()&&events[i].first==x){
            delta+=events[i++].second;
        }
        active+=delta;
        maximum=std::max(maximum,active);
        previous=x;
    }
    std::cout<<covered<<' '<<maximum<<'\n';
}

Complexity analysis

O(n log n) time for sorting 2n events and O(n) event storage. The grouped scan is O(n), with O(1) active state. Covered length is at most the total coordinate span.

Example input and output

Read n (0..100000), then n integer endpoint pairs within ±10^6. Treat normalized intervals as half-open; ignore zero length. Print union length and maximum overlap on positive-length regions.

Input

3
1 4
2 6
6 8

Output

7 2

The union is [1,8), length 7; only the slab [2,4) is covered twice.

Practical applications

Use event sweeps for interval coverage, offline queries and spatial problems where only a small part of the state changes at each coordinate. The next lessons add a Fenwick tree and a covered-length segment tree to this framework.

Check your understanding

Which active count determines coverage between previousX and x?

Put it into practice

Test disjoint, nested, identical and endpoint-touching intervals.