Interval Scheduling: Sort by End Time

EditorialUpdated Oct 25, 2026

One room, as many meetings as possible

There's one meeting room and a pile of requests, each with a start and an end time. The day can't stretch, so you want to say yes to as many meetings as possible, with no two in the room at once. A meeting may start the moment another ends.

The sure way is to try every set of meetings and keep the biggest one that fits:

import itertools

def most_meetings_brute(meetings):
    best = 0
    for mask in range(1 << len(meetings)):      # every subset: in or out, for each meeting
        chosen = [m for k, m in enumerate(meetings) if mask >> k & 1]
        if all(a[1] <= b[0] or b[1] <= a[0] for a, b in itertools.combinations(chosen, 2)):
            best = max(best, len(chosen))
    return best

It works on a handful. But n meetings have 2ⁿ subsets: 20 meetings have 1,048,576. On our judge, 20 meetings with no clashes took 9.3 seconds in Python, and 30 would mean a billion subsets.

The faster way is to decide one meeting at a time: pick one by some rule, cross out everything it clashes with, repeat. The question is which rule. Three sensible ones fail:

Earliest start. On [[1, 10], [2, 3], [4, 5]] it took [1, 10] first and kept 1, but [2, 3] and [4, 5] fit together: 2.
Shortest first. On [[1, 5], [4, 7], [6, 10]] it took [4, 7], which clashes with both others, and kept 1. [1, 5] and [6, 10] fit: 2.
Fewest conflicts. On an input of 11 meetings it took [9, 13], which clashes with only two, and kept 3. The best is 4: [0, 4], [6, 10], [12, 16] and [18, 22], which clash with three or four others each.

The rule that works is earliest end: keep the meeting that frees the room soonest, then the next one that starts after it ends. On those three inputs it kept 2, 2, 4, the best every time.

Three rows on a timeline from 0 to 14. A best schedule: [2, 6], [7, 9] and [10, 13]. The meeting that ends first of all: [1, 4]. Swap it in: [1, 4], [7, 9] and [10, 13]. Guides mark 4, where [1, 4] ends, 6, where [2, 6] ended, and 7, where [7, 9] starts: 4 ≤ 6 ≤ 7, still 3 meetings and none clash.

Why the earliest end never misses

Take any best schedule and look at its first meeting, the one that ends first in it. Now take the meeting that ends first of all, and swap it in. It ends no later than the meeting it replaces, and every other meeting in the schedule starts after that one ended, so after this one ends too. Nothing clashes, and the count is the same.

So some best schedule starts with the earliest end. Keep it, cross out what it clashes with, and what's left is the same question on fewer meetings: the same swap works again. That's the whole proof, and the whole algorithm: sort by end, and keep each meeting that starts once the room is free.

Keep the Earliest End — Meetings sorted by end. Green ones are kept, dashed ones clash and are skipped, and the amber line shows when the room is free again.

int mostMeetings(vector<vector<int>> meetings) {
    sort(meetings.begin(), meetings.end(),
         [](const vector<int>& a, const vector<int>& b) { return a[1] < b[1]; });   // by end
    int kept = 0;
    long long freeAt = LLONG_MIN;                  // the room is free from freeAt on
    for (const auto& m : meetings) {
        if (m[0] >= freeAt) {                      // starts once the room is free: keep it
            kept++;
            freeAt = m[1];
        }
    }
    return kept;
}

def most_meetings(meetings):
    kept, free_at = 0, float("-inf")            # the room is free from free_at on
    for start, end in sorted(meetings, key=lambda m: m[1]):   # by end
        if start >= free_at:                    # starts once the room is free: keep it
            kept += 1
            free_at = end
    return kept

static int mostMeetings(int[][] meetings) {
    int[][] sorted = meetings.clone();
    Arrays.sort(sorted, (a, b) -> Integer.compare(a[1], b[1]));   // by end
    int kept = 0;
    long freeAt = Long.MIN_VALUE;                  // the room is free from freeAt on
    for (int[] m : sorted) {
        if (m[0] >= freeAt) {                      // starts once the room is free: keep it
            kept++;
            freeAt = m[1];
        }
    }
    return kept;
}

function mostMeetings(meetings) {
    const sorted = [...meetings].sort((a, b) => a[1] - b[1]);   // by end
    let kept = 0, freeAt = -Infinity;              // the room is free from freeAt on
    for (const [start, end] of sorted) {
        if (start >= freeAt) {                     // starts once the room is free: keep it
            kept++;
            freeAt = end;
        }
    }
    return kept;
}

Each prints 2, 2, 4, 3, 1, 1, 3 and 4, the same as trying every subset, on the three inputs above and five more. The sort is O(n log n) and the pass is O(n).

Now try to beat it. Keep meetings yourself, let each rule pick on a preset built to break it, and use the swap on any schedule you've made.

Keep the Most: keep meetings by hand, race the four rules, and swap in the earliest end

Removals, and when touching counts

Non-overlapping Intervals asks for the fewest intervals to remove so the rest don't overlap. That's the same question from the other side: remove everything a best schedule leaves out.

def erase_overlap_intervals(intervals):
    return len(intervals) - most_meetings(intervals)   # remove what a best schedule leaves out

It returned 1, 2 and 0 for [[1, 2], [2, 3], [3, 4], [1, 3]], three copies of [1, 2], and [[1, 2], [2, 3]]. That last one needs no removal, because this problem lets intervals touch.

Not every problem does. In Activity Selection a meeting has to start after the previous one finishes. And when you're stabbing intervals with points, like arrows bursting balloons, touching intervals share the point, so one arrow gets both. Then the test is start > free_at: with it, [[1, 2], [2, 3]] counts as 1 group and [[1, 3], [2, 4], [5, 6]] as 2. Read the statement for which one you have, the way Introduction to Intervals did for merging.

One day per event

Maximum Number of Events That Can Be Attended bends the rule. Each event runs over a range of days and you can go on any one of them, one event per day. Nothing has to be skipped whole any more; the question is which event gets today.

The same idea answers it: today, go to the open event that ends soonest, because it has the fewest days left. Walk the days in order. Each morning, add the events that start today to a min-heap of end days, throw out the ones that already ended, and attend the one on top.

One Event a Day — Each bar covers an event's days; the amber line is today. Amber events are open, the indigo one is attended today, green ones were attended, and dashed ones ran out of days.

import heapq

def max_events(events):
    events = sorted(events)                     # by start day
    open_ends, i, attended = [], 0, 0           # a min-heap of end days of events that have started
    for day in range(1, max(end for _, end in events) + 1):
        while i < len(events) and events[i][0] == day:
            heapq.heappush(open_ends, events[i][1])     # it starts today
            i += 1
        while open_ends and open_ends[0] < day:
            heapq.heappop(open_ends)            # it ended before today: too late for it
        if open_ends:
            heapq.heappop(open_ends)            # attend the one that ends soonest
            attended += 1
    return attended

It returned 4 for [[1, 3], [1, 1], [2, 4], [2, 2], [3, 4]], 3 for [[1, 1], [1, 3], [2, 2]] and 2 for [[1, 1], [1, 1], [2, 3]], where one of the two one-day events has to miss out. Each event enters and leaves the heap once: O((n + D) log n) for n events over D days.

Sorting by end and heaps in your language

Sorting by end needs a key or a comparator in every language: a plain sort orders by start, which is the rule that fails. Maximum Number of Events also needs a min-heap, the smallest end on top:

Language	Sort by end	A min-heap
C++	a lambda on `a[1] < b[1]`	`priority_queue<int, vector<int>, greater<int>>`
Python	`key=lambda m: m[1]`	`heapq`
Java	`(a, b) -> Integer.compare(a[1], b[1])`	`PriorityQueue`
JavaScript	`(a, b) => a[1] - b[1]`	none built in

C++'s plain priority_queue<int> is a max-heap: holding 5, 1 and 4, its top() was 5. With greater<int>, as in the table, the top was 1.
JavaScript has no heap built in. Write a small binary heap, or the event problem turns O(n²) once you keep a sorted array instead.

Spotting it

Clues:

the most intervals with no overlap, or the fewest to remove so none overlap;
one resource used by one thing at a time: a room, a machine, a person;
points stabbing intervals: arrows, or the fewest moments that touch every interval;
one per day, where each item can go on any day of its range.

And the near-misses:

meetings with values, keeping the most valuable set: greedy fails, since one long meeting can be worth more than two short ones. That's dynamic programming (Maximum Profit in Job Scheduling, in Dynamic Programming).
every meeting must happen, in the fewest rooms: that's the most meetings at one moment (Counting Overlaps with a Sweep Line).
combining overlaps into one interval: merging (Introduction to Intervals).

Common mistakes

Sorting by start. key=lambda m: m[0]

A long meeting that starts early blocks everything under it: [[1, 10], [2, 3], [4, 5]] kept 1; the answer is 2.

> where touching is allowed. if start > free_at:

Non-overlapping Intervals lets one interval end where the next starts, so [[1, 2], [2, 3]] needs no removal. With > it removed 1.

Returning what's kept. The question asks how many to remove: on [[1, 2], [2, 3], [3, 4], [1, 3]] that returned 3; the answer is 1.

Attending events in start order. Each event on its first free day, in start order

[1, 3] takes day 2 and leaves [2, 2] nothing: [[1, 1], [1, 3], [2, 2]] gave 2; the answer is 3.

Never dropping ended events. Without the open_ends[0] < day loop the heap hands back an event that's already over and counts it: [[1, 1], [1, 1], [2, 3]] gave 3; the answer is 2.

Check yourself

Quiz

1 / 6

Multiple choice

Which rule keeps the most meetings in one room, every time?

Practice problems

From easier to harder:

Activity Selection: sort by end, keep each meeting that starts after the last one finishes.
Non-overlapping Intervals: n minus the most you can keep, touching allowed.
Maximum Number of Events That Can Be Attended: day by day, the open event that ends soonest.

Next, Counting Overlaps with a Sweep Line: when every meeting has to happen, how many rooms does it take?