AlgoScope

Intervals and Greedy Choices

Put every interval on a timeline, one per row, and the classic greedy problems become visible. To fit as many non-overlapping intervals as possible, sort by finish time and keep whatever starts after the last one you kept ended: finishing early leaves the most room for the rest, and no other choice can beat it. To count the rooms a set of meetings needs, sweep the timeline and count how many are open at once. The peak is the answer, because that many overlap at that moment. Assigning rooms is the same sweep with a twist: each meeting takes the first room that is free by its start.

The player

Sweep over 6 intervals.012345678910abcdefaaabbbccccdddeeeefff

How many rooms do 6 meetings need? Sweep time from left to right. A meeting that starts takes a room, one that ends gives it back, and the most rooms ever taken at once is the answer. Rows are sorted by start. At equal times an end is processed before a start.

Check your understanding

The player pauses before each decision in this run and asks what happens next. Here are all 12, with their answers.

  1. Next event at t = 0: a starts. Open meetings go to?

    • 1
    • 3

    Answer: 1. A start adds one.

  2. Next event at t = 1: b starts. Open meetings go to?

    • 0
    • 2

    Answer: 2. A start adds one.

  3. Next event at t = 2: c starts. Open meetings go to?

    • 1
    • 3

    Answer: 3. A start adds one.

  4. Next event at t = 3: a ends. Open meetings go to?

    • 2
    • 4

    Answer: 2. An end subtracts one.

  5. Next event at t = 4: b ends. Open meetings go to?

    • 1
    • 3

    Answer: 1. An end subtracts one.

  6. Next event at t = 4: d starts. Open meetings go to?

    • 0
    • 2

    Answer: 2. A start adds one.

  7. Next event at t = 5: e starts. Open meetings go to?

    • 1
    • 3

    Answer: 3. A start adds one.

  8. Next event at t = 6: c ends. Open meetings go to?

    • 2
    • 4

    Answer: 2. An end subtracts one.

  9. Next event at t = 7: d ends. Open meetings go to?

    • 1
    • 3

    Answer: 1. An end subtracts one.

  10. Next event at t = 8: f starts. Open meetings go to?

    • 0
    • 2

    Answer: 2. A start adds one.

  11. Next event at t = 9: e ends. Open meetings go to?

    • 1
    • 3

    Answer: 1. An end subtracts one.

  12. Next event at t = 11: f ends. Open meetings go to?

    • 0
    • 2

    Answer: 0. An end subtracts one.

How it runs, step by step

  1. How many rooms do 6 meetings need? Sweep time from left to right. A meeting that starts takes a room, one that ends gives it back, and the most rooms ever taken at once is the answer. Rows are sorted by start. At equal times an end is processed before a start.

    Sweep over 6 intervals.

  2. t = 0: a starts, taking a room. Open meetings: 1. That is a new maximum, so at least 1 rooms are needed.

    Time 0, a starts, 1 open.

  3. t = 1: b starts, taking a room. Open meetings: 2. That is a new maximum, so at least 2 rooms are needed.

    Time 1, b starts, 2 open.

  4. t = 2: c starts, taking a room. Open meetings: 3. That is a new maximum, so at least 3 rooms are needed.

    Time 2, c starts, 3 open.

  5. t = 3: a ends, freeing a room. Open meetings: 2.

    Time 3, a ends, 2 open.

  6. t = 4: b ends, freeing a room. Open meetings: 1.

    Time 4, b ends, 1 open.

  7. t = 4: d starts, taking a room. Open meetings: 2.

    Time 4, d starts, 2 open.

  8. t = 5: e starts, taking a room. Open meetings: 3.

    Time 5, e starts, 3 open.

  9. t = 6: c ends, freeing a room. Open meetings: 2.

    Time 6, c ends, 2 open.

  10. t = 7: d ends, freeing a room. Open meetings: 1.

    Time 7, d ends, 1 open.

  11. t = 8: f starts, taking a room. Open meetings: 2.

    Time 8, f starts, 2 open.

  12. t = 9: e ends, freeing a room. Open meetings: 1.

    Time 9, e ends, 1 open.

  13. t = 11: f ends, freeing a room. Open meetings: 0.

    Time 11, f ends, 0 open.

  14. 3 rooms. At the peak 3 meetings overlapped, so fewer rooms cannot work, and the sweep never needs more than the peak. Sorting the 2n endpoints dominates: O(n log n).

    3 rooms needed.

The code

Intervals and Greedy Choices, in Python

def select(intervals):
    chosen = []
    last_end = 0
    for start, end in sorted(intervals, key=lambda p: p[1]):    # earliest finish first
        if start >= last_end: chosen.append((start, end)); last_end = end    # fits after the last kept
    return chosen

def rooms(intervals):
    events = [ev for s, e in intervals for ev in ((s, +1), (e, -1))]
    events.sort(key=lambda ev: (ev[0], ev[1]))                  # ends before starts at a tie
    open_rooms = 0; best = 0
    for _, delta in events: open_rooms += delta; best = max(best, open_rooms)
    return best

def partition(intervals):
    room_ends = []                                              # when each room frees up
    assigned = []
    for start, end in sorted(intervals, key=lambda p: p[0]):
        room = next((i for i, t in enumerate(room_ends) if t <= start), -1)    # first room that is free
        if room >= 0: room_ends[room] = end; assigned.append(room)
        else: room_ends.append(end); assigned.append(len(room_ends) - 1)
    return assigned

def job_sequencing(jobs):                                # job = (deadline, profit), one slot each
    by_profit = sorted(jobs, key=lambda j: j.profit, reverse=True)    # greedy: richest first
    slots = [None] * max(j.deadline for j in jobs)
    for job in by_profit:
        t = job.deadline - 1                             # the latest slot it can take
        while t >= 0 and slots[t] is not None: t -= 1    # walk back to a free one
        if t >= 0: slots[t] = job                        # nothing free before the deadline: skip it
    return list(slots)

Intervals and Greedy Choices, in JavaScript

function select(intervals) {
  const chosen = [];
  let lastEnd = 0;
  for (const [start, end] of [...intervals].sort((a, b) => a[1] - b[1])) {   // earliest finish first
    if (start >= lastEnd) { chosen.push([start, end]); lastEnd = end; }      // fits after the last kept
  }
  return chosen;
}

function rooms(intervals) {
  const events = intervals.flatMap(([s, e]) => [[s, +1], [e, -1]]);
  events.sort((a, b) => a[0] - b[0] || a[1] - b[1]);                         // ends before starts at a tie
  let open = 0, best = 0;
  for (const [, delta] of events) { open += delta; best = Math.max(best, open); }
  return best;
}

function partition(intervals) {
  const roomEnds = [];                                                  // when each room frees up
  const assigned = [];
  for (const [start, end] of [...intervals].sort((a, b) => a[0] - b[0])) {
    const room = roomEnds.findIndex((t) => t <= start);                 // first room that is free
    if (room >= 0) { roomEnds[room] = end; assigned.push(room); }
    else { roomEnds.push(end); assigned.push(roomEnds.length - 1); }
  }
  return assigned;
}

function jobSequencing(jobs) {                               // job = (deadline, profit), one slot each
  const byProfit = [...jobs].sort((a, b) => b.profit - a.profit);   // greedy: richest first
  const slots = new Array(Math.max(...jobs.map((j) => j.deadline))).fill(null);
  for (const job of byProfit) {
    let t = job.deadline - 1;                                // the latest slot it can take
    while (t >= 0 && slots[t] !== null) t--;                 // walk back to a free one
    if (t >= 0) slots[t] = job;                              // nothing free before the deadline: skip it
  }
  return [...slots];
}

Intervals and Greedy Choices, in Kotlin

fun select(intervals: List<Pair<Int, Int>>): List<Pair<Int, Int>> {
    val chosen = mutableListOf<Pair<Int, Int>>()
    var lastEnd = 0
    for ((start, end) in intervals.sortedBy { it.second }) {   // earliest finish first
        if (start >= lastEnd) { chosen += start to end; lastEnd = end }   // fits after the last kept
    }
    return chosen
}

fun rooms(intervals: List<Pair<Int, Int>>): Int {
    val events = intervals.flatMap { (s, e) -> listOf(s to +1, e to -1) }
        .sortedWith(compareBy({ it.first }, { it.second }))                // ends before starts at a tie
    var open = 0; var best = 0
    for ((_, delta) in events) { open += delta; best = maxOf(best, open) }
    return best
}

fun partition(intervals: List<Pair<Int, Int>>): List<Int> {
    val roomEnds = mutableListOf<Int>()                                 // when each room frees up
    return intervals.sortedBy { it.first }.map { (start, end) ->
        val room = roomEnds.indexOfFirst { it <= start }                // first room that is free
        if (room >= 0) { roomEnds[room] = end; room } else { roomEnds += end; roomEnds.size - 1 }
    }
}

fun jobSequencing(jobs: List<Job>): List<Job?> {              // job = (deadline, profit), one slot each
    val byProfit = jobs.sortedByDescending { it.profit }      // greedy: richest first
    val slots = arrayOfNulls<Job>(jobs.maxOf { it.deadline })
    for (job in byProfit) {
        var t = job.deadline - 1                                // the latest slot it can take
        while (t >= 0 && slots[t] != null) t--                  // walk back to a free one
        if (t >= 0) slots[t] = job                              // nothing free before the deadline: skip it
    }
    return slots.toList()
}

This lesson has no write-it-yourself editor. It is free, like every lesson, and nothing here is locked.

Remember

  • Interval scheduling: sort by finish time, keep each interval that starts at or after the last kept end.
  • Meeting rooms: sweep sorted endpoints, +1 on a start and -1 on an end. The peak count is the answer.
  • Ends sort before starts at the same time, so a room freed at t can be reused at t.

Where this is used

Register allocation in compilersCompilers

A compiler lays the instructions out in a line and gives every value a live interval covering the stretch where it is still needed. The number of registers a program wants at a point is the number of live intervals overlapping there, so the meeting rooms question is literally the register question, and linear scan assigns each interval the first register free at its start, exactly like partition. HotSpot's C1 JIT allocates this way. When no register is free the value spills to memory, which is the case where you would have to open another room.

Exclusion constraints on range typesDatabases

PostgreSQL stores a booking as a single tsrange column and an exclusion constraint rejects any insert whose range overlaps an existing one for the same room. The overlap test runs against a GiST index, so the check stays fast instead of scanning every other booking. This moves the no-two-intervals-overlap invariant out of application code and into the database, where two concurrent bookings for the same slot cannot both win.

Genome interval toolsBioinformatics

A BED file is nothing but intervals on a chromosome, stored half-open exactly like the convention this lesson uses. bedtools merge requires input presorted by chromosome and start, because it collapses overlapping features in a single forward pass. bedtools intersect does not require sorting by default. It loads one file into an in-memory R-tree instead, and the -sorted flag switches it to the same streaming sweep, which is what keeps memory flat on huge files. On a file with tens of millions of aligned reads, that is the difference between holding one cursor per file and holding the whole file in memory.

Deadline scheduling in the Linux kernelOperating systems

SCHED_DEADLINE runs whichever runnable task has the nearest absolute deadline, the same greedy shape as taking the earliest finish, and on a single CPU that rule is optimal by an exchange argument: if any order meets every deadline then this one does. The kernel also refuses to admit a task whose bandwidth would push the sum of runtime over period past the capacity it accounts for, which by default is 95 percent of the CPUs in the scheduling domain. That admission test is the capacity question rather than the ordering question, the same split as counting rooms versus assigning them. Media playback and robotics use it because a frame delivered late is as useless as one never delivered.

Why it works this way

Why sort by finish time, and not by start time or by shortest first?

Every other obvious key has a counterexample. Sorting by start time lets one interval that begins at 9 and runs all day knock out everything behind it. Shortest first can pick a brief interval in the middle that straddles two longer ones which do not overlap each other, trading two for one. Earliest finish survives an exchange argument: take any optimal set, swap its first interval for the one that finishes earliest, and the set is still valid and still the same size. Repeat that swap and any optimum turns into the greedy answer, so the greedy answer was already optimal.

Ends sort before starts only because the intervals are half-open

Putting the end event first treats an interval as [start, end), so a meeting that ends at 10 does not conflict with one that starts at 10 and the room is reused. If your endpoints are inclusive on both sides, such as a booking held on days 3 to 5 against one on days 5 to 7, that really is a conflict and the tie has to sort starts first instead. The same assumption is baked into select: start >= lastEnd is the half-open test, and closed intervals need start > lastEnd. Getting the tie backwards only goes wrong on inputs whose endpoints touch, so it slips through casual testing, and it is not always off by one: four closed meetings, two running 1 to 5 and two running 5 to 9, all overlap at time 5, but ends-before-starts reports a peak of 2 instead of 4.

Why the peak overlap is exactly the room count, not just a lower bound

One half is easy: at the busiest instant k meetings are all in progress and no two of them can share a room, so k rooms are necessary. The other half is what partition proves: a meeting only opens a brand new room when every existing room is still busy at its start, which means all of those meetings plus this one overlap at that moment, so the room count can never exceed the peak. Most greedy algorithms only give you one of those halves and you settle for an approximation. Here the bound and the algorithm meet, so the sweep's peak is the exact answer.

Why job sequencing walks backwards from the deadline

Each job takes the latest free slot at or before its deadline, never the earliest. Filling from the front would burn slot 0 on a job due at time 5 and leave nothing for a job due at time 1. Filling from the back keeps the tight early slots free for jobs that have nowhere else to go. The cost is that the backward walk is a linear scan, so a long run of taken slots makes the whole thing O(n * maxDeadline) in the worst case. Pointing each slot at the next free slot below it with a disjoint-set brings that back to near linear.

Read more

Next up

Fast and Slow Pointers

Find the middle of seven

Next lesson: Fast and Slow Pointers