Scheduling and resource allocation

What is a greedy algorithm?

A greedy algorithm repeatedly makes a locally best choice and commits to it. It does not explore every combination or undo earlier choices. A greedy rule is correct only when you can explain why taking it still permits a globally best answer. A choice that looks best immediately can otherwise lead to a worse final result.

Example: To schedule the largest number of non-overlapping meetings, choose a meeting that finishes earliest, then repeat among meetings that start after it. Finishing early leaves as much room as possible for later meetings.

Helpful before this chapter

If these ideas are new, begin with:

Sorting and selection

Understand the idea

Scheduling and resource allocation have distinct objectives: maximum compatible count, minimum rooms, or weighted profit. Sorting by finish fits count; sorting events or maintaining ending-time heaps fits simultaneous resources.

Work through an example

[1,4),[2,3),[3,5) need two rooms, because the middle ending at 3 can share with the last starting at 3. Half-open endpoints allow touching.

Time and space complexity

Typical O(n log n) sorting/heap work; O(n) events or peak-resource storage.

Why it works

Active resources correspond exactly to intervals started but not yet ended.

Common mistakes

Room minimization does not discard meetings.
Closed endpoints require different equal-time handling.

Chapter lab · Python implementation

Greedy commits to a local choice without revisiting it. This requires a proof: a tempting rule can fail even on tiny inputs. Our lab selects the maximum number of nonoverlapping half-open intervals by earliest finishing time, then checks array reachability by maintaining the farthest reachable index.

This shared lab connects the chapter's topics. Follow the current lesson's worked example first, then trace the complete implementation. Additional algorithms described in topic exercises are variations you can implement independently.

def schedule(intervals):
    chosen=[]; end=float('-inf')
    for start,finish in sorted(intervals,key=lambda x:x[1]):
        if start>finish: raise ValueError('invalid interval')
        if start>=end:
            chosen.append((start,finish)); end=finish
    return chosen

def can_jump(values):
    if not values: return False
    if any(x<0 for x in values): raise ValueError('nonnegative jumps required')
    farthest=0
    for i,jump in enumerate(values):
        if i>farthest: return False
        farthest=max(farthest,i+jump)
        if farthest>=len(values)-1: return True
    return False

Run and test the lab

Copy the implementation and these assertions into a Python 3 file and run it. An assertion failure means the actual result differs from the expectation. Add the current topic's exercise and boundary tests to deepen your understanding.

assert len(schedule([(1,4),(2,3),(3,5),(5,7)]))==3
assert can_jump([2,3,1,1,4])
assert not can_jump([3,2,1,0,4])
assert can_jump([0]) and not can_jump([])

CHECK YOUR UNDERSTANDING