Fewest bookings to cancel so none clash

Keeping the most bookings is the same as cancelling the fewest. Sort by end time and keep each booking that starts no earlier than the last kept one ends; cancel the rest. Finishing earliest leaves the most room for what follows. O(n log n) time, O(n) space for the sorted copy.

Sorting by end is the template for 'keep the most intervals that do not overlap'.

Sorting by start fails: one long early booking blocks many short ones.

The exchange argument: swap the first booking of any best answer for the earliest-ending one; nothing later clashes.

def fewest_cancels(bookings: list[list[int]]) -> int:
    kept_end = None  # end time of the last booking kept
    cancels = 0
    for start, end in sorted(bookings, key=lambda b: b[1]):
        if kept_end is not None and start < kept_end:
            cancels += 1  # clashes: drop it, keep the earlier finish
        else:
            kept_end = end
    return cancels

fun fewestCancels(bookings: List<List<Int>>): Int {
    var keptEnd: Int? = null // end time of the last booking kept
    var cancels = 0
    for (b in bookings.sortedBy { it[1] }) {
        val end = keptEnd
        if (end != null && b[0] < end) cancels++ else keptEnd = b[1]
    }
    return cancels
}

Common mistakes

• Sorting by start or by length.
• Treating touching bookings as clashing when the question says they do not.

State the exchange argument in one sentence; it is the proof interviewers want.

Follow-up questions

Think of your answer first, then open the hint.

1. How many arrows hit a set of balloons on a line?

   Show hint

   The same sort by end; one arrow per kept interval, with touching counted as shared.

2. What if bookings have values?

   Show hint

   Weighted interval scheduling: DP over bookings sorted by end, with binary search for the last compatible one.