Interval Scheduling (Max Non-Overlapping)

Given a list of intervals, return the maximum number of non-overlapping intervals you can select.

Intervals are half-open: [start, end). Two intervals do not overlap if prev.End <= next.Start.

Types

type Interval struct {
    Start int
    End   int
}

Function signature

func MaxNonOverlapping(intervals []Interval) int

Example

intervals = [{1,3},{2,4},{3,5},{0,7},{5,6}]
output = 3  // pick [1,3), [3,5), [5,6)

Constraints

• 0 <= len(intervals) <= 200000
• -1_000_000_000 <= Start < End <= 1_000_000_000

Notes

• A greedy strategy that sorts by end time is optimal.