🎓 A1Learner
🔍
0 of 47 lessons completed

Scheduling with Intervals

Scheduling with intervals is picking the largest set of time ranges that do not overlap. Each picked range must start at or after the previous picked range ends.

Recognition signal

A problem fits this pattern when it asks for the most ranges that fit without overlapping. One room and many requests is the classic shape of the question.

signals = [
    "Asks for the most ranges that fit.",
    "Picked ranges must not overlap.",
    "One room, many requests."
]
for line in signals:
    print(line)

Template: sort by end, pick greedily

The template sorts by end time and picks each range that starts at or after the last picked end. Picking the earliest end first is the pattern in plain words.

def schedule(intervals):
    ordered = sorted(intervals, key=lambda item: item[1])
    picked = []
    last_end = -1
    for start, end in ordered:
        if start >= last_end:
            picked.append([start, end])
            last_end = end
    return picked

picked = schedule([[1, 3], [2, 4], [3, 5], [0, 6], [5, 7]])
print(picked)
print("Count:", len(picked))

Worked problem: all ranges fit

When no ranges overlap, every range is picked. The template still checks each range against the last picked end before taking it.

def schedule(intervals):
    ordered = sorted(intervals, key=lambda item: item[1])
    picked = []
    last_end = -1
    for start, end in ordered:
        if start >= last_end:
            picked.append([start, end])
            last_end = end
    return picked

picked = schedule([[1, 2], [2, 3], [3, 4]])
print("Count:", len(picked))

Example

def schedule(intervals):
    ordered = sorted(intervals, key=lambda item: item[1])
    picked = []
    last_end = -1
    for start, end in ordered:
        if start >= last_end:
            picked.append([start, end])
            last_end = end
    return picked

print(schedule([[9, 10], [9, 12], [10, 11], [11, 13]]))

Key points

  • Interval: a pair holding a start and an end.
  • Greedy choice: at each step, pick the range that ends earliest among the ranges left.
  • Sort by end time first, so the earliest-ending range comes first.
  • Keep the end of the last picked range, and skip any range that starts before it.

Sorting by end gives 9 to 10, then 10 to 11, then 9 to 12, then 11 to 13. The first two are picked, 9 to 12 is skipped since it starts before 11, and 11 to 13 is picked last.

Note

the earliest end leaves the most room for later ranges, which is why this choice works.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

Why sort by end time first?