Interval Scheduling Maximization

Given intervals, select the maximum number of non-overlapping intervals.

Greedy approach: always pick the interval that ends earliest.

function maxNonOverlapping(intervals)
    sort intervals by end time
    count := 0
    lastEnd := -infinity

    for interval in intervals
        if interval.start >= lastEnd then
            count := count + 1
            lastEnd := interval.end

    return count

Why greedy works: picking the earliest-ending interval leaves the most room for future intervals. Any other choice can only do worse.

Time: $O(n \log n)$. Space: $O(1)$.