Interval Scheduling

Given $n$ intervals, select the maximum number of pairwise non-overlapping ones.

The algorithm — sort by finish time

int maxNonOverlapping(vector<pair<int,int>> iv) {         // (start, end)
    sort(iv.begin(), iv.end(), [](auto& a, auto& b){ return a.second < b.second; });
    int count = 0, lastEnd = INT_MIN;
    for (auto& [s, e] : iv)
        if (s >= lastEnd) { count++; lastEnd = e; }
    return count;
}

$O(n\log n)$, dominated by the sort.

Why earliest finish time

Greedy stays ahead: after $k$ picks, greedy’s $k$-th interval finishes no later than the $k$-th interval of any optimal solution, so greedy always has at least as much room left. See Exchange Arguments for the full proof.

The other sort keys are wrong

• Earliest start — one very long interval blocks everything.
• Shortest duration — a short interval in the middle can block two long ones.
• Fewest conflicts — plausible, but constructible counterexamples exist.

Only earliest finish time is optimal.

The variants

Problem	Method	Cost
Max count of non-overlapping	greedy by finish time	$O(n\log n)$
Min intervals to remove	$n$ − the above	$O(n\log n)$
Max weight non-overlapping	DP + binary search	$O(n\log n)$
Min rooms to host all	interval partitioning — max overlap	$O(n\log n)$
Max intervals with $\le k$ overlapping at once	greedy + a min-heap of size $k$	$O(n\log n)$
Cover a segment with the fewest intervals	greedy: extend as far right as possible	$O(n\log n)$
$k$ non-overlapping sets, max total	min-cost flow, or a DP	varies
Max non-overlapping on a circle	fix one interval, then linear; $O(n^2\log n)$

Minimum intervals to cover $[L,R]$

sort(iv.begin(), iv.end());                               // by start
int cur = L, i = 0, cnt = 0;
while (cur < R) {
    int best = cur;
    while (i < n && iv[i].first <= cur) best = max(best, iv[i++].second);
    if (best == cur) return -1;                            // gap: impossible
    cur = best; cnt++;
}

Each step takes the interval reaching furthest right among those that start at or before the current position. The same “jump as far as possible” greedy solves the jump-game family.

Endpoints: open or closed?

Decide whether intervals touching at a point conflict:

• Closed $[s,e]$, touching conflicts → the condition is s > lastEnd.
• Half-open $[s,e)$, touching is fine → the condition is s >= lastEnd.

Read the statement. “A meeting ending at 3 and one starting at 3” is the standard ambiguity, and getting it backwards fails exactly one test.

Related sweep problems

Question	Method
Maximum simultaneous overlap	sort $+1$/$-1$ events, running maximum
Total covered length	sort by start, merge overlapping
Points covered by the most intervals	the same sweep
For each point, how many intervals cover it	difference array
Intervals containing a query point	offline sweep + a set
Merge overlapping intervals	sort by start, extend or emit

// maximum simultaneous overlap
vector<pair<int,int>> ev;
for (auto& [s, e] : iv) { ev.push_back({s, 1}); ev.push_back({e, -1}); }
sort(ev.begin(), ev.end());                                // -1 before +1 at equal times
int cur = 0, best = 0;
for (auto& [t, d] : ev) { cur += d; best = max(best, cur); }

The tie-break at equal times (-1 before +1) encodes the half-open convention — the same decision as above.

See also: Weighted Interval Scheduling · Interval Partitioning · Exchange Arguments