Sweep Line

Concept

Sweep line processes events sorted by position (or time). For interval problems, create +1 events at interval starts and -1 events at interval ends. Sort all events, then sweep through them maintaining a running counter. The maximum counter value is the maximum overlap.

When to Use

• ▸Maximum number of overlapping intervals at any point
• ▸Restaurant/meeting room scheduling (max concurrent events)
• ▸Finding the busiest time period
• ▸Any problem involving interval overlap counting

Intuition

Imagine a timeline. When an interval starts, someone enters the room (+1). When it ends, someone leaves (-1). Sort all enter/leave events by time. Walk through them in order, keeping a running count of people in the room. The peak count is the maximum overlap. Custom sort ensures that at the same time, exits (-1) are processed before entries (+1) to handle boundary cases correctly.

Complexity

Template Code

#include<bits/stdc++.h>
using namespace std;

bool cmp(pair<int, int> a, pair<int, int> b){
    if(a.first == b.first) return a.second > b.second;
    return a.first < b.first;
}

int main(){
    ios_base::sync_with_stdio(0), cin.tie(0);

    int n;
    cin >> n;

    vector<pair<int, int>> ev;
    int start, end;
    for(int i = 0; i < n; i++){
        cin >> start >> end;

        ev.push_back({start, 1});
        ev.push_back({end, -1});
    }

    sort(ev.begin(), ev.end(), cmp);

    int cnt = 0, mx = 0;
    for(auto &x : ev){
        cnt += x.second;
        mx = max(mx, cnt);
    }

    cout << mx;
    return 0;
}

// Sample Input:
// 4
// 1 4
// 2 6
// 4 7
// 5 8
//
// Sample Output:
// 3