Disjoint Intervals

You're handed a calendar full of meetings, and some of them clash. You want to cancel as few meetings as possible so that none of the survivors overlap. disjointIntervals(intervals) takes an array of [start, end] pairs and returns the minimum number of intervals you must remove so the rest are mutually non-overlapping. This is the classic non-overlapping intervals problem, the removal-counting twin of activity selection.

Signature

// intervals: an array of [start, end] pairs, each a half-open interval [start, end)
// returns: the minimum count of intervals to remove so the rest never overlap
function disjointIntervals(intervals: [number, number][]): number;

Examples

disjointIntervals([[1, 2], [2, 3], [3, 4], [1, 3]]);
// → 1
// Remove [1, 3] and the rest — [1,2], [2,3], [3,4] — are all disjoint.

disjointIntervals([[1, 2], [2, 3], [3, 4]]);
// → 0
// Already non-overlapping; nothing to remove. (Touching at an endpoint is fine.)

disjointIntervals([[1, 2], [1, 2], [1, 2]]);
// → 2
// All three occupy the same slot. Keep one, remove the other two.

Notes

• Minimum removals — you return a count, not the surviving intervals and not the ones you removed. Just how many had to go.
• Half-open intervals — treat each [start, end] as [start, end). Two intervals that merely touch at an endpoint, like [1, 2] and [2, 3], do not overlap. Overlap requires the second to start strictly before the first one ends.
• Empty input — disjointIntervals([]) returns 0. A single interval also returns 0; one interval can never clash with itself.
• Don't worry about — input validation, unsorted input (you sort it yourself), or returning which intervals to drop. Just the count.