Job Scheduling with Two Jobs Allowed at a Time

Job Scheduling with Two Jobs Allowed at a Time is a classic greedy interval problem. You have two identical machines and a pile of jobs, and you want to run as many as possible — but a machine can only do one job at a time.

The slow way first

The brute-force temptation is to try every assignment of jobs to machines — for each job, both machines or skip — and keep the best. That is O(2ⁿ) combinations, hopelessly slow.

The question to ask: if I process jobs in a sensible order, can I make each decision locally and never regret it? For intervals, the magic order is almost always by start time.

The idea: sort by start, track two free-times

Sort the jobs by start time. Keep two numbers, free_a and free_b — the time each machine next becomes available (both start at negative infinity). For each job in order:

• If start >= free_a, machine A is free — run the job there and set free_a = end.
• Else if start >= free_b, machine B is free — run it there and set free_b = end.
• Else both machines are busy — reject the job.

The key insight: by going in start order, the machine that frees up earliest is always the safest place to put the next job, so a simple two-way check is enough — no backtracking.

Walk through it

Step through the animation. The pointer scans jobs left to right (already start-sorted). The two machine free-times update underneath. Job [3,6] lands when both machines are still busy (A until 4, B until 5), so it is rejected. Job [6,8] fits A again because A freed up at 4.

Pseudocode

sort jobs by start time
free_a = free_b = -infinity        # when each machine is next available
count = 0
for each job [start, end] in jobs:
    if start >= free_a:            # machine A is free
        free_a = end
        count += 1
    else if start >= free_b:       # machine B is free
        free_b = end
        count += 1
    else:
        skip                       # both busy -> reject
return count

The Python solution

def schedule(jobs):
    jobs.sort(key=lambda j: j[0])
    free_a = free_b = float("-inf")
    count = 0
    for start, end in jobs:
        if start >= free_a:
            free_a = end
            count += 1
        elif start >= free_b:
            free_b = end
            count += 1
        # else: no machine free, reject
    return count

• jobs.sort(key=lambda j: j[0]) orders the jobs by start time — the whole greedy argument depends on this.
• free_a and free_b are the times each machine becomes available; both begin at negative infinity so the first jobs always fit.
• start >= free_a asks: did machine A finish its last job before this one begins? If yes, A is free.
• We only fall through to machine B when A is busy, and we only reject when both are busy.
• count tracks how many jobs we managed to schedule.

Complexity

After the sort, the scan is a single pass with only two machine variables, so the extra space is constant. The sort dominates, giving O(n log n) overall.

When this pattern shows up

Practice