Greedy choices and intervals cheat sheet

Combine overlapping bookings into blocks

Sort by start. Walk through the bookings keeping the list of blocks; if a booking starts at or before the last block's end, extend that block's end; otherwise start a new block. Sorting costs O(n log n) and the walk O(n); the sorted copy and the blocks take O(n) space.

def merge_bookings(bookings: list[list[int]]) -> list[list[int]]:
    blocks: list[list[int]] = []
    for start, end in sorted(bookings):
        if blocks and start <= blocks[-1][1]:  # touches the last block
            blocks[-1][1] = max(blocks[-1][1], end)
        else:
            blocks.append([start, end])
    return blocks

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.

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

How many rooms do the bookings need at once?

Turn each booking into two events: +1 at its start and -1 at its end. Sort the events by time, with ends before starts at the same time (half-open). Sweep through, keeping a running count; the largest count is the answer. O(n log n) time and O(n) space. A min-heap of end times gives the same result.

def rooms_needed(bookings: list[list[int]]) -> int:
    events: list[tuple[int, int]] = []
    for start, end in bookings:
        events.append((start, 1))
        events.append((end, -1))  # ends sort before starts at a tie
    in_use = most = 0
    for _, change in sorted(events):
        in_use += change
        most = max(most, in_use)
    return most

Add a booking to a sorted list of separate blocks

Three phases in one pass: copy the blocks that end before the new one starts; absorb every block that starts at or before the new one's end by widening it; then copy the rest. O(n) time and O(n) space for the output, no sort needed because the input is already sorted.

def add_booking(blocks: list[list[int]],
                new: list[int]) -> list[list[int]]:
    out: list[list[int]] = []
    start, end = new
    i = 0
    while i < len(blocks) and blocks[i][1] < start:  # wholly before
        out.append(blocks[i])
        i += 1
    while i < len(blocks) and blocks[i][0] <= end:  # touches: absorb
        start, end = min(start, blocks[i][0]), max(end, blocks[i][1])
        i += 1
    out.append([start, end])
    return out + blocks[i:]

Can you hop to the last tile?

Track the furthest tile you can reach so far. Walk the tiles in order; if the current tile is beyond that reach, you are stuck. Otherwise update reach = max(reach, i + hops[i]). One pass, O(n) time, O(1) memory.

def can_reach_end(hops: list[int]) -> bool:
    furthest = 0  # every tile up to here can be reached
    for i, h in enumerate(hops):
        if i > furthest:
            return False
        furthest = max(furthest, i + h)
    return True

Fewest hops to the last tile

Think in layers: the tiles reachable with k hops form a range. While scanning the current range, track the furthest tile reachable with one more hop. When the scan reaches the end of the range, take a hop and the new range ends at that furthest tile. O(n) time, O(1) memory.

def fewest_hops(hops: list[int]) -> int:
    count = layer_end = furthest = 0
    for i in range(len(hops) - 1):  # no hop needed from the last tile
        furthest = max(furthest, i + hops[i])
        if i == layer_end:  # this layer is done: take a hop
            count += 1
            layer_end = furthest
    return count

Where to start a delivery loop so the van never runs dry

If total fuel is less than total cost, no start works. Otherwise walk once, keeping a running tank; whenever it drops below zero, no stop from the current start up to here can be a start, so restart from the next stop with an empty tank. The last restart point is the answer. O(n) time, O(1) memory.

def loop_start(fuel: list[int], cost: list[int]) -> int:
    if sum(fuel) < sum(cost):
        return -1
    start = tank = 0
    for i, (got, spent) in enumerate(zip(fuel, cost)):
        tank += got - spent
        if tank < 0:  # no stop from start to i can begin the loop
            start, tank = i + 1, 0
    return start

Cut a string into the most chunks so no letter crosses a cut

Record the last index of every letter. Scan left to right, stretching the current piece's end to the last index of each letter you see. When the scan reaches that end, no letter in the piece appears later, so cut there. O(n) time and O(alphabet) memory.

def chunk_sizes(text: str) -> list[int]:
    last = {ch: i for i, ch in enumerate(text)}  # final positions
    sizes: list[int] = []
    begin = end = 0
    for i, ch in enumerate(text):
        end = max(end, last[ch])
        if i == end:  # nothing in this piece appears later
            sizes.append(i - begin + 1)
            begin = i + 1
    return sizes

Largest total of a contiguous run

Keep the best total of a run ending at the current value: either extend the previous run or start fresh here, whichever is bigger. Track the best seen overall. One pass, O(n) time, O(1) memory. This is Kadane's algorithm.

def best_run(vals: list[int]) -> int:
    run = best = vals[0]
    for v in vals[1:]:
        run = max(v, run + v)  # keep the run only while it helps
        best = max(best, run)
    return best

When does a greedy choice work?

A greedy algorithm makes the locally best choice and never revisits it. It is correct when you can show an exchange argument: take any optimal answer, swap its first choice for the greedy one, and show the result is still optimal. Then repeat. If a small counterexample breaks the rule, use DP instead.

Sort intervals by start or by end?

Sort by start when you are combining or inserting: overlapping intervals become neighbours. Sort by end when you are choosing the most intervals that do not overlap: finishing earliest leaves the most room. For 'how many at once', sort start and end events together.

Sweep-line thinking

A sweep line turns intervals into events (start and end points), sorts them, and walks through them in order while maintaining a running state: a count, a set of active items or a running total. It solves peak overlap, total covered length, free gaps and 'which items are active at time t' questions in O(n log n).