Activity selection and interval partitioning

Activity selection asks for the most activities one room can hold when no two may overlap. The greedy answer is to sort the activities by finish time and keep each one that starts at or after the finish of the last one kept: one sort and one scan, O(n log n). Interval partitioning asks the opposite question. Every activity must run, so how few rooms will do, and which room gets each one? Sort by start instead, keep the rooms in a min-heap ordered by the minute each becomes free, and give each activity the room that frees earliest if it is already free, or a new room if it is not. The rooms used then equal the most activities running at one moment, which no plan can beat. Both shortcuts stop working once activities carry different values, such as fees, and dynamic programming takes over.

Two questions about one Saturday

1. The eight requests in the figure: one room holds five of them, and all eight run in three rooms.
2. [(600, 660), (660, 720)]: back to back, so one room holds both.
3. A single batch: one kept, in room 1.

The brute force, and why it fails at these sizes

For question 1, try the subsets from the largest down until one has no overlap. For question 2, try one room, then two, then three, each time with every way of putting each batch in a room:

import math
from itertools import combinations, product

SATURDAY = [(480, 600), (540, 630), (600, 660), (615, 735), (660, 720), (690, 810), (720, 780), (780, 870)]


def fits(batches):
    """No two of these batches overlap (half-open, so back to back is fine)."""
    ordered = sorted(batches)
    return all(earlier[1] <= later[0] for earlier, later in zip(ordered, ordered[1:]))


def most_by_subsets(batches):
    """Tries the subsets from the largest down; returns the best size and how many subsets it checked."""
    checked = 0
    for size in range(len(batches), 0, -1):
        for chosen in combinations(batches, size):
            checked += 1
            if fits(chosen):
                return size, checked
    return 0, checked


def rooms_by_assignments(batches):
    """Tries 1 room, then 2, ...: every way to put each batch in a room; returns the rooms and the plans tried per k."""
    tried = []
    for k in range(1, len(batches) + 1):
        tried.append(0)
        for plan in product(range(k), repeat=len(batches)):
            tried[-1] += 1
            if all(fits([b for b, r in zip(batches, plan) if r == room]) for room in range(k)):
                return k, tried
    return 0, tried


size, checked = most_by_subsets(SATURDAY)
print(f"one room: {size} batches, after checking {checked} of the {2 ** len(SATURDAY)} subsets")
k, tried = rooms_by_assignments(SATURDAY)
steps = [f"{t:,} plan{'s' * (t != 1)} with {r} room{'s' * (r != 1)}" for r, t in enumerate(tried, 1)]
print(f"every batch: {k} rooms, after trying {', '.join(steps)}")
for n in (20, 40):
    print(f"{n} batches: {2 ** n:.1e} subsets, and {3 ** n:.1e} plans with 3 rooms")
print(f"100,000 batches: 2 ** 100,000 subsets, a number of {math.floor(100_000 * math.log10(2)) + 1:,} digits")

one room: 5 batches, after checking 66 of the 256 subsets
every batch: 3 rooms, after trying 1 plan with 1 room, 256 plans with 2 rooms, 901 plans with 3 rooms
20 batches: 1.0e+06 subsets, and 3.5e+09 plans with 3 rooms
40 batches: 1.1e+12 subsets, and 1.2e+19 plans with 3 rooms
100,000 batches: 2 ** 100,000 subsets, a number of 30,103 digits

Eight batches already cost 66 subsets and 1,158 room plans. Each extra batch doubles the subsets and triples the plans for three rooms: 40 batches mean about 10¹² subsets and 10¹⁹ plans, and 100,000 batches a number of subsets with 30,103 digits. A quadratic method for question 1, comparing every pair of batches once, needs about n²/2 = 5 × 10⁹ steps at n = 100,000.

What to notice

• The batch that ends first is a safe first pick for one room. Any best plan starts with a batch that ends no earlier, so swapping it for the first finisher loses nothing.
• A crowded moment sets a floor. From 10:15 to 10:30 physics, chemistry and English all run, so no plan can use fewer than three rooms.

The key idea: two greedy scans

Activity selection, earliest finish first. Sort the batches by end. Keep the first, then keep each batch that starts at or after the end of the last batch kept, and skip the rest. On Saturday the scan keeps maths, chemistry, biology, Hindi and economics, five batches back to back. The test is >=, because a batch may start in the minute the last one ends.

Interval partitioning, earliest start first. Sort the batches by start and keep a min-heap of (minute free, room number) pairs, one per room opened. Each batch looks only at the top of the heap. If that room is free by the batch’s start, the batch takes it; if even the room that frees earliest is still busy, every room is, and the batch opens a new one. That is one sort plus one or two heap operations per batch, O(n log n) in all. The Saturday run:

Three rooms is the floor that the crowded moment set, so no plan does better.

Other rules, and fees. Some rules look as good and are not. Earliest start first keeps the batch that starts first. Shortest first keeps the shortest batch. Fewest clashes first keeps the batch that overlaps the fewest others. For rooms, end order fills rooms in order of finish instead of start. When batches pay fees, the goal becomes the most money. Highest fee first keeps the dearest batch; best fee per minute keeps the batch that pays most for each minute. Both fail, and so does earliest end. A dynamic programme over the batches sorted by end, with binary search, finds the best total in O(n log n).

Exercise: a room for every batch

assign_rooms([(480, 600), (540, 630), (600, 660)])  # for example [1, 2, 1]: 2 rooms
assign_rooms([(600, 660), (660, 720)])              # [1, 1]: back to back fits in one room
assign_rooms([])                                    # []

def assign_rooms(batches):
    """A room number (1, 2, 3 ...) for every batch, in the order given, using the fewest rooms."""
    # Replace this line with your code.
    return None

import random

from rooms import assign_rooms


def rooms_needed(batches):
    """The most batches running in one minute: no plan can use fewer rooms."""
    events = sorted([(end, -1) for _, end in batches] + [(start, 1) for start, _ in batches])
    running = peak = 0
    for _, change in events:
        running += change
        peak = max(peak, running)
    return peak


def check(batches, room):
    """The plan has one room per batch, numbers 1 to k with none skipped, no clash, and the fewest rooms."""
    assert isinstance(room, list) and len(room) == len(batches), f"one room number per batch, got {room!r}"
    used = sorted(set(room))
    assert used == list(range(1, len(used) + 1)), f"rooms must be numbered 1, 2, 3 ... with none skipped: {used}"
    by_room = {}
    for (start, end), r in zip(batches, room):
        by_room.setdefault(r, []).append((start, end))
    for r, held in by_room.items():
        held.sort()
        for (s1, e1), (s2, e2) in zip(held, held[1:]):
            assert e1 <= s2, f"room {r} holds ({s1}, {e1}) and ({s2}, {e2}), which overlap"
    assert len(used) == rooms_needed(batches), f"{len(used)} rooms, but {rooms_needed(batches)} are enough"


def by_search(batches):
    """A search the tests trust: the fewest rooms over every plan (small lists only)."""
    def place(i, ends, k):
        if i == len(batches):
            return True
        start, end = batches[i]
        for r in range(len(ends)):
            if all(e <= start or end <= s for s, e in ends[r]):
                ends[r].append((start, end))
                if place(i + 1, ends, k):
                    return True
                ends[r].pop()
        if len(ends) < k:
            ends.append([(start, end)])
            if place(i + 1, ends, k):
                return True
            ends.pop()
        return False

    return next(k for k in range(len(batches) + 1) if place(0, [], k))


def test_prompt_examples():
    """the three examples of the prompt"""
    for batches in ([(480, 600), (540, 630), (600, 660)], [(600, 660), (660, 720)], []):
        check(batches, assign_rooms(batches))


def test_saturday():
    """eight batches of one Saturday, which need 3 rooms"""
    saturday = [(480, 600), (540, 630), (600, 660), (615, 735), (660, 720), (690, 810), (720, 780), (780, 870)]
    room = assign_rooms(saturday)
    check(saturday, room)
    assert max(room) == 3


def test_identical_and_nested():
    """copies of one batch each need a room; a batch inside another shares no room with it"""
    check([(600, 660)] * 4, assign_rooms([(600, 660)] * 4))
    check([(0, 100), (10, 20), (30, 40), (20, 30)], assign_rooms([(0, 100), (10, 20), (30, 40), (20, 30)]))


def test_long_batch_beside_short_ones():
    """one long batch and twenty short ones back to back: 2 rooms"""
    batches = [(10 * k, 10 * k + 10) for k in range(20)] + [(0, 200)]
    room = assign_rooms(batches)
    check(batches, room)
    assert max(room) == 2


def test_input_unchanged():
    """the caller's list keeps its order"""
    batches = [(660, 720), (480, 600), (600, 660)]
    assign_rooms(batches)
    assert batches == [(660, 720), (480, 600), (600, 660)]


def test_hundred_thousand_batches():
    """100,000 batches with times up to 10**9"""
    rng = random.Random(4)
    batches = []
    for _ in range(100_000):
        start = rng.randrange(10**9 - 10**6)
        batches.append((start, start + rng.randint(1, 10**5)))
    check(batches, assign_rooms(batches))


def test_against_search():
    """300 random lists against the fewest rooms over every plan"""
    rng = random.Random(23)
    for _ in range(300):
        batches = []
        for _ in range(rng.randint(1, 7)):
            start = rng.randrange(10)
            batches.append((start, rng.randint(start + 1, 10)))
        room = assign_rooms(batches)
        check(batches, room)
        assert max(room) == by_search(batches), f"assign_rooms({batches})"

Why both scans are optimal, checked by exhaustive search Pro: opens with a Pro, Premium or Ultimate pass

Both scans in five languages, run on 100,000 requests Pro: opens with a Pro, Premium or Ultimate pass

Rules that fail, and fees that need dynamic programming Pro: opens with a Pro, Premium or Ultimate pass

Interview questions

Key takeaways

• Activity selection: sort by finish and keep each batch that starts once the last kept one has ended.
• Interval partitioning: sort by start, then reuse the room that frees earliest or open a new one.
• The rooms used equal the most batches running at one moment, and no plan can use fewer.
• With fees per batch, the greedy rules fail and dynamic programming takes over.