Sweep Line (Difference Array)

Concept

Instead of sorting events as pairs, use a difference array (or map). For each interval [l, r], do diff[l] += 1 and diff[r+1] -= 1. Then take the prefix sum of the diff array — the value at each index tells you how many intervals cover that point. This avoids custom sorting and is simpler when coordinates are small integers.

When to Use

  • ▸Counting overlapping intervals on integer coordinates
  • ▸Range increment queries (add +1 to range [l, r])
  • ▸When coordinate range is bounded and fits in an array
  • ▸Simpler alternative to pair-based sweep line

Intuition

Think of it as turning on a light at the start of each interval and turning it off just after the end. The difference array records +1 for "on" and -1 for "off". Running a prefix sum then tells you how many lights are on at each position. For large/sparse coordinates, use a map instead of an array — it only stores the positions that matter.

Complexity

Time
O(n + R) array / O(n log n) map
Space
O(R) array / O(n) map

Template Code

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

// ============================
// Version 1: Array (small coordinate range)
// ============================

// int main(){
//     ios_base::sync_with_stdio(0), cin.tie(0);
//
//     int n, R;
//     cin >> n >> R;
//
//     vector<int> diff(R+2, 0);
//     for(int i = 0; i < n; i++){
//         int l, r;
//         cin >> l >> r;
//         diff[l] += 1;
//         diff[r+1] -= 1;
//     }
//
//     int mx = 0, cur = 0;
//     for(int i = 0; i <= R; i++){
//         cur += diff[i];
//         mx = max(mx, cur);
//     }
//
//     cout << mx << "\n";
//
//     return 0;
// }

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

// ============================
// Version 2: Map (large/sparse coordinates)
// ============================

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

    int n;
    cin >> n;

    map<int, int> diff;
    for(int i = 0; i < n; i++){
        int l, r;
        cin >> l >> r;
        diff[l] += 1;
        diff[r+1] -= 1;
    }

    int mx = 0, cur = 0;
    for(auto &[pos, val] : diff){
        cur += val;
        mx = max(mx, cur);
    }

    cout << mx << "\n";

    return 0;
}

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