INVARIANT · INTERVALS · SORT THE ENDS, SWEEP THE LINE
01
00/15
01 / COVER MODULE 22 · INTERVALS
INVARIANT · MODULE 22 · INTERVALS
SORT THE ENDS, SWEEP THE LINE

An interval problem asks what overlaps what. Sorted, only neighbours can overlap, and a sweep from left to right needs to remember only what is still open: the last end, a count, a heap of ends or a set of heights. Eleven moves, fifteen problems.

15Problems
5Families
11Units
12Live walks
← → ↑ ↓  or  W A S D  navigate SPACE next   DOUBLE-CLICK to advance I index   G goto problem   P predict H hide solutions   F fullscreen
INVARIANT · INTERVALS · SORT THE ENDS, SWEEP THE LINE · INTERVALS
02 / INDEX PRESS I FROM ANYWHERE

INDEX — ALL 15 PROBLEMS

Click any problem to jump straight to it. Solved ones turn green. Press I from anywhere to come back here. The number is the problem's fixed number in this deck, not a slide position.

MERGE AND INTERSECT · 02
SORT BY END · 04
COUNT WHAT IS OPEN · 03
A HEAP OF WHAT ENDS NEXT · 04
SEARCH THE SORTED ENDS · 02
SOLVED HAS A JUDGE LINK
INVARIANT · INTERVALS · SORT THE ENDS, SWEEP THE LINE · INTERVALS
03 / MECHANISM UNIT 01 · MERGE WHAT OVERLAPS THE NEW ONE

COPY, MERGE, COPY

The sorted list splits into three runs around the new interval. Those ending before it are copied, those starting no later than its end are folded into it, and the rest are copied.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · INTERVALS · SORT THE ENDS, SWEEP THE LINE · INTERVALS
04 / DRILL UNIT 01 · Merge What Overlaps the New One

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

insert([[1, 3], [6, 9]], [2, 5])?

[1, 3] ends at 3, not before 2, so it merges: [1, 5]. [6, 9] starts after 5 and is copied.

DRILL 02 · RECALL

Why does the merge loop test start ≤ hi rather than start < hi?

[1, 5] and [5, 7] both contain 5, so they are one interval, [1, 7]. With < they would stay apart.

INVARIANT · INTERVALS · SORT THE ENDS, SWEEP THE LINE · INTERVALS
05 / PROBLEM #01 · MERGE · MED

Insert Interval

MED merge ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

A list of intervals, sorted and disjoint, gets one more. Insert it and merge whatever it overlaps.

INTUITION

The sorted list falls into three runs. Intervals that end before the new one starts are copied as they are. Intervals that start no later than it ends overlap it, so they are folded into it, stretching its ends. Whatever is left starts after it ends and is copied too. Each interval is read once.

STEPS
  1. Copy every interval whose end is before the new start
  2. While an interval starts at or before the new end, widen the new one to cover it
  3. Append the widened interval
  4. Copy the rest
BRUTEO(n log n) appending it and merging the whole list again
→
OPTIMALO(n)
↕ SCROLL
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
    vector<vector<int>> out;
    int i = 0, n = intervals.size();
    while (i < n && intervals[i][1] < newInterval[0])      // ends before it starts
        out.push_back(intervals[i++]);
    while (i < n && intervals[i][0] <= newInterval[1]) {   // overlaps it: merge
        newInterval[0] = min(newInterval[0], intervals[i][0]);
        newInterval[1] = max(newInterval[1], intervals[i][1]);
        i++;
    }
    out.push_back(newInterval);
    while (i < n) out.push_back(intervals[i++]);           // starts after it ends
    return out;
}
TIMEO(n)one pass over the sorted list
SPACEO(n)the answer
TRAP

An interval that only touches the new one. The intervals are closed, so [1, 5] and [5, 7] share the point 5 and become [1, 7]. The merge test is start ≤ hi, not start < hi.

INVARIANT · INTERVALS · SORT THE ENDS, SWEEP THE LINE · INTERVALS
06 / MECHANISM UNIT 02 · KEEP THE ONE THAT ENDS FIRST

KEEP THE ONE THAT ENDS FIRST

Sort by end. The interval ending first is a safe keep, since it leaves the most room for everything after it. Each later interval is kept if it starts once the last kept one ends.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · INTERVALS · SORT THE ENDS, SWEEP THE LINE · INTERVALS
07 / DRILL UNIT 02 · Keep the One That Ends First · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

eraseOverlapIntervals([[1, 2], [2, 3], [3, 4], [1, 3]])?

By end: [1, 2], [2, 3], [1, 3], [3, 4]. The first two touch and are kept, [1, 3] starts before 3 and goes, and [3, 4] is kept.

DRILL 02 · RECALL

Why sort by end rather than by start?

Any best plan can swap its first interval for the one ending first: it ends no later, so the rest of the plan still fits.

INVARIANT · INTERVALS · SORT THE ENDS, SWEEP THE LINE · INTERVALS
08 / PROBLEM #02 · END · MED

Non-overlapping Intervals

MED end ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Remove the fewest intervals so that the rest do not overlap. Touching at an endpoint is allowed.

INTUITION

Removing the fewest is keeping the most. Sort by end. The interval that ends first is always safe to keep. Any best plan can swap its own first interval for this one, which ends no later and so leaves at least as much room. Keep it, skip whatever starts before it ends, and repeat from the next one that starts after.

STEPS
  1. Sort by end
  2. end = −∞, the end of the last kept interval
  3. An interval starting at or after end is kept, and end becomes its end
  4. Any other overlaps a kept one: it is removed
BRUTEO(2ⁿ · n) trying every set of intervals to keep
→
OPTIMALO(n log n)
↕ SCROLL
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end(),
         [](const vector<int>& a, const vector<int>& b) { return a[1] < b[1]; });   // by end
    int kept = 0, end = INT_MIN;
    for (auto& v : intervals)
        if (v[0] >= end) { kept++; end = v[1]; }   // starts once the last kept one ends
    return intervals.size() - kept;
}
TIMEO(n log n)the sort, then one pass
SPACEO(1)beyond the sort
TRAP

Sorting by start. The interval that starts first can be the longest. On [1, 10], [2, 3], [4, 5] it keeps [1, 10] and removes two, when removing [1, 10] alone is enough.

INVARIANT · INTERVALS · SORT THE ENDS, SWEEP THE LINE · INTERVALS
09 / PROBLEM #03 · END · EASY

Movie Festival

EASY end ▶ SOLVE ON CSESCSES does not rate its problems; the chip is this deck's estimate. Submit the Python tab as PyPy3.
SIGNAL — WHAT GIVES IT AWAY

Movies have start and end times. Watch the most movies entirely; one may start the moment another ends.

INTUITION

It is unit 2 counting what it keeps. Sort the movies by end and watch every movie that starts at or after the end of the last one watched. The movie ending first is a safe first choice, since it frees the evening soonest.

STEPS
  1. Read the movies as (end, start) and sort
  2. end = 0, when the last watched movie ends
  3. A movie starting at or after end is watched; end becomes its end
  4. Print the count
BRUTEO(2ⁿ · n) trying every set of movies
→
OPTIMALO(n log n)
↕ SCROLL
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; scanf("%d", &n);
    vector<pair<int, int>> m(n);               // (end, start)
    for (auto& p : m) scanf("%d %d", &p.second, &p.first);
    sort(m.begin(), m.end());                  // the earliest end first
    int cnt = 0, end = 0;
    for (auto& p : m)
        if (p.second >= end) { cnt++; end = p.first; }   // it starts once the last one ends
    printf("%d\n", cnt);
}
TIMEO(n log n)the sort, then one pass
SPACEO(n)the movies
TRAP

A strict comparison. A movie that starts exactly when the last one ends can be watched. With s > end, the sample's 3–5 and 5–8 count as a clash and the answer drops from 2 to 1.

INVARIANT · INTERVALS · SORT THE ENDS, SWEEP THE LINE · INTERVALS
10 / DRILL UNIT 02 · Keep the One That Ends First · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

Movie Festival with (start, end) = (1, 2), (2, 3), (1, 5), (3, 4), (4, 6)?

By end: 1–2, 2–3, 3–4, then 1–5, which starts before 4 and is skipped, then 4–6. Each watched movie starts as the last one ends.

INVARIANT · INTERVALS · SORT THE ENDS, SWEEP THE LINE · INTERVALS
11 / MECHANISM UNIT 03 · ONE ARROW AT THE FIRST END

SHOOT AT THE FIRST END

Sort by end. The balloon ending first needs an arrow at or before its end, and its end hits everything an earlier spot would. A balloon starting past the arrow needs a new one.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · INTERVALS · SORT THE ENDS, SWEEP THE LINE · INTERVALS
12 / DRILL UNIT 03 · One Arrow at the First End · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

findMinArrowShots([[10, 16], [2, 8], [1, 6], [7, 12]])?

By end: [1, 6], [2, 8], [7, 12], [10, 16]. An arrow at 6 bursts the first two; one at 12 bursts the other two.

DRILL 02 · TRACE

findMinArrowShots([[1, 2], [2, 3], [3, 4], [4, 5]])?

An arrow at 2 bursts [1, 2] and [2, 3], which touch. [3, 4] starts past it, so an arrow at 4 bursts the last two.

INVARIANT · INTERVALS · SORT THE ENDS, SWEEP THE LINE · INTERVALS
13 / PROBLEM #04 · END · MED

Minimum Number of Arrows to Burst Balloons

MED end ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Balloons span [start, end] along a line. An arrow at x bursts every balloon covering x. Burst them all with the fewest arrows.

INTUITION

Sort by end. Some arrow must burst the balloon that ends first, and it must fly at or before that end. Flying exactly at the end hits every balloon the earlier spots would, and maybe more. So shoot there, skip every balloon that starts at or before it, and shoot again at the end of the first balloon it misses.

STEPS
  1. Sort by end
  2. at = −∞, where the last arrow flew
  3. A balloon starting after at was missed, so shoot at its end
  4. One that starts at or before at is already burst
BRUTEO(n²) shooting at every end in turn, after a sort
→
OPTIMALO(n log n)
↕ SCROLL
int findMinArrowShots(vector<vector<int>>& points) {
    sort(points.begin(), points.end(),
         [](const vector<int>& a, const vector<int>& b) { return a[1] < b[1]; });   // by end
    int arrows = 0;
    long long at = LLONG_MIN;                  // where the last arrow flew
    for (auto& p : points)
        if (p[0] > at) { arrows++; at = p[1]; }   // missed it: shoot at its end
    return arrows;
}
TIMEO(n log n)the sort, then one pass
SPACEO(1)beyond the sort
TRAP

Sorting by subtraction. The ends run from −2³¹ to 2³¹ − 1, so a[1] - b[1] overflows and the sort comes out wrong. Compare with Integer.compare in Java and < in C++.

INVARIANT · INTERVALS · SORT THE ENDS, SWEEP THE LINE · INTERVALS
14 / PROBLEM #05 · END · HARD

Segments

HARD end ▶ SOLVE ON CODEFORCESCodeforces 22D, rated 1900.
SIGNAL — WHAT GIVES IT AWAY

Segments lie on a line, with their ends in either order. Drive the fewest nails at integer points so that every segment holds one, and print where.

INTUITION

It is unit 3 with nails for arrows, and the ends are integers, so the nails are too. Sort by right end. The segment that ends first needs a nail at or before its right end, and its right end hits every segment an earlier point would. A segment whose left end is past the last nail needs a new one.

STEPS
  1. Read each segment as (right, left), swapping ends that come reversed
  2. Sort by right end
  3. A segment whose left end is past the last nail gets a nail at its right end
  4. Print the count and the nails
BRUTEO(2ᵏ · n) trying every set of the k distinct right ends
→
OPTIMALO(n log n)
↕ SCROLL
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; scanf("%d", &n);
    vector<pair<int, int>> s(n);               // (right, left)
    for (auto& p : s) {
        int a, b; scanf("%d %d", &a, &b);
        p = make_pair(max(a, b), min(a, b));   // the ends may come in either order
    }
    sort(s.begin(), s.end());                  // the earliest right end first
    vector<int> nails;
    for (auto& p : s)
        if (nails.empty() || p.second > nails.back())   // not nailed yet
            nails.push_back(p.first);          // nail it at its right end
    printf("%d\n", (int)nails.size());
    for (int x : nails) printf("%d ", x);
    printf("\n");
}
TIMEO(n log n)the sort, then one pass
SPACEO(n)the segments and the nails
TRAP

Trusting the order of the ends. The second sample writes a segment as 4 2. Read 10 1 that way and it sorts by 1 and takes a nail at 1; beside [5, 6] that costs two nails where one at 6 hits both. Swap each pair so that left ≤ right.

INVARIANT · INTERVALS · SORT THE ENDS, SWEEP THE LINE · INTERVALS
15 / DRILL UNIT 03 · One Arrow at the First End · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

In Segments, why is each pair of ends sorted before anything else?

The second sample writes one segment as 4 2. Read 10 1 as given and it sorts by 1 and gets a nail at 1. Beside [5, 6] that makes two nails, when one at 6 hits both.

INVARIANT · INTERVALS · SORT THE ENDS, SWEEP THE LINE · INTERVALS
16 / MECHANISM UNIT 04 · TWO SORTED LISTS, TWO POINTERS

THE ONE THAT ENDS FIRST IS DONE

Two intervals meet on [later start, earlier end] when that is not empty. Then whichever ends first cannot meet anything later in the other list, so its pointer moves.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · INTERVALS · SORT THE ENDS, SWEEP THE LINE · INTERVALS
17 / DRILL UNIT 04 · Two Sorted Lists, Two Pointers

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

intervalIntersection([[1, 3], [5, 9]], [[2, 6]])?

[1, 3] and [2, 6] meet on [2, 3]; [1, 3] ends first and moves on. [5, 9] and [2, 6] meet on [5, 6].

DRILL 02 · RECALL

After comparing a[i] and b[j], which pointer moves?

Everything after it in the other list starts later still, past its end, so it can meet nothing more. The other interval may still meet the next one.

INVARIANT · INTERVALS · SORT THE ENDS, SWEEP THE LINE · INTERVALS
18 / PROBLEM #06 · MERGE · MED

Interval List Intersections

MED merge ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Two lists of closed intervals, each sorted and disjoint. Return every intersection of an interval in one with an interval in the other.

INTUITION

Look at the current interval of each list. They meet on [later start, earlier end] when that is not empty. Then the one that ends first is finished, because everything after it in the other list starts later still, past its end. Move that pointer and look again.

STEPS
  1. i = j = 0
  2. lo = the later start, hi = the earlier end
  3. If lo ≤ hi, [lo, hi] is an intersection
  4. Advance whichever interval ends first
BRUTEO(m · n) intersecting every pair
→
OPTIMALO(m + n)
↕ SCROLL
vector<vector<int>> intervalIntersection(vector<vector<int>>& firstList,
                                         vector<vector<int>>& secondList) {
    vector<vector<int>> out;
    int i = 0, j = 0, m = firstList.size(), n = secondList.size();
    while (i < m && j < n) {
        int lo = max(firstList[i][0], secondList[j][0]);   // the later start
        int hi = min(firstList[i][1], secondList[j][1]);   // the earlier end
        if (lo <= hi) out.push_back({lo, hi});
        if (firstList[i][1] < secondList[j][1]) i++;      // the one that ends first is done
        else j++;
    }
    return out;
}
TIMEO(m + n)each pointer moves m or n times
SPACEO(1)beyond the answer
TRAP

Dropping a single point. [0, 5] and [5, 10] meet at 5, and the answer must list [5, 5]. The test is lo ≤ hi; with lo < hi the sample loses two of its six intersections.

INVARIANT · INTERVALS · SORT THE ENDS, SWEEP THE LINE · INTERVALS
19 / MECHANISM UNIT 05 · COUNT WHAT IS OPEN

A +1 AND A −1 PER INTERVAL

The count of what is open changes only at a start or an end. Sort those 2n events, walk them with a running count, and keep its largest value.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · INTERVALS · SORT THE ENDS, SWEEP THE LINE · INTERVALS
20 / DRILL UNIT 05 · Count What Is Open · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

Restaurant Customers with (arrive, leave) = (1, 6), (2, 3), (4, 8), (5, 7)?

Events: 1+, 2+, 3−, 4+, 5+, 6−, 7−, 8−. The count runs 1, 2, 1, 2, 3, 2, 1, 0.

DRILL 02 · RECALL

Why does minGroups close an interval at right + 1?

[1, 5] covers 5. Closing it at 5 would let its close sort before [5, 8]'s open, and the two would seem to fit in one group.

INVARIANT · INTERVALS · SORT THE ENDS, SWEEP THE LINE · INTERVALS
21 / PROBLEM #07 · COUNT · EASY

Restaurant Customers

EASY count ▶ SOLVE ON CSESCSES does not rate its problems; the chip is this deck's estimate. Submit the Python tab as PyPy3.
SIGNAL — WHAT GIVES IT AWAY

Customers arrive and leave at distinct times. What is the most customers in the restaurant at once?

INTUITION

The count only changes at an arrival or a departure, so look only there. Turn each customer into two events, +1 at arrival and −1 at departure, and sort the 2n events by time. Walk them in order with a running count; its largest value is the answer.

STEPS
  1. Make an event (a, +1) and an event (b, −1) for each customer
  2. Sort the events by time
  3. Add each event's +1 or −1 to cur
  4. Keep the largest cur
BRUTEO(n²) counting, at each arrival, who is inside
→
OPTIMALO(n log n)
↕ SCROLL
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; scanf("%d", &n);
    vector<pair<int, int>> ev;                 // (time, +1 arrives or -1 leaves)
    for (int i = 0; i < n; i++) {
        int a, b; scanf("%d %d", &a, &b);
        ev.push_back(make_pair(a, 1));
        ev.push_back(make_pair(b, -1));
    }
    sort(ev.begin(), ev.end());                // every time is distinct
    int cur = 0, best = 0;
    for (auto& e : ev) {
        cur += e.second;                       // one more customer, or one fewer
        best = max(best, cur);
    }
    printf("%d\n", best);
}
TIMEO(n log n)sorting 2n events
SPACEO(n)the events
TRAP

A counter for every minute. The times reach 10⁹, so an array indexed by time does not fit. Only the 2n event times matter: sort them.

INVARIANT · INTERVALS · SORT THE ENDS, SWEEP THE LINE · INTERVALS
22 / PROBLEM #08 · COUNT · MED

Divide Intervals Into Minimum Number of Groups

MED count ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Split inclusive intervals into the fewest groups so that no two in a group intersect; [1, 5] and [5, 8] do.

INTUITION

No grouping can use fewer groups than the most intervals covering one point, since those all need different groups. That many is also enough: hand out groups in order of start, reusing any group whose last interval has ended. So count the most open at once, with the sweep of unit 5. Ends are inclusive, so an interval closes at right + 1.

STEPS
  1. Make (left, +1) and (right + 1, −1) for each interval
  2. Sort; at one time −1 sorts before +1
  3. Sweep with a running count
  4. Return its largest value
BRUTEO(n²) counting, at each left end, the intervals covering it
→
OPTIMALO(n log n)
↕ SCROLL
int minGroups(vector<vector<int>>& intervals) {
    vector<pair<int, int>> ev;
    for (auto& v : intervals) {
        ev.push_back(make_pair(v[0], 1));      // it opens at left
        ev.push_back(make_pair(v[1] + 1, -1)); // and is closed from right + 1 on
    }
    sort(ev.begin(), ev.end());                // at one time, -1 sorts before +1
    int cur = 0, best = 0;
    for (auto& e : ev) {
        cur += e.second;
        best = max(best, cur);                 // the most open at once
    }
    return best;
}
TIMEO(n log n)sorting 2n events
SPACEO(n)the events
TRAP

Closing at right instead of right + 1. Then [1, 5]'s close at 5 sorts before [5, 8]'s open at 5, and the two seem to fit in one group though both hold the point 5.

INVARIANT · INTERVALS · SORT THE ENDS, SWEEP THE LINE · INTERVALS
23 / DRILL UNIT 05 · Count What Is Open · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

minGroups([[1, 5], [5, 8], [8, 9]])?

[1, 5] and [5, 8] share 5, and [5, 8] and [8, 9] share 8, so two groups: {[1, 5], [8, 9]} and {[5, 8]}.

INVARIANT · INTERVALS · SORT THE ENDS, SWEEP THE LINE · INTERVALS
24 / MECHANISM UNIT 06 · ROOMS

A HEAP OF DEPARTURES

Take guests by arrival and keep (departure, room) in a min-heap. If the room that frees first is free before this arrival, reuse it; if even that one is busy, every room is.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · INTERVALS · SORT THE ENDS, SWEEP THE LINE · INTERVALS
25 / MECHANISM UNIT 06 · DELAYS

A HEAP OF FREE ROOMS, A HEAP OF BUSY ONES

Free rooms by number say which room to take; busy rooms by end say which frees first. With no room free, a meeting waits for that one and keeps its length.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · INTERVALS · SORT THE ENDS, SWEEP THE LINE · INTERVALS
26 / DRILL UNIT 06 · Which Room Frees First · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

Room Allocation with (arrive, depart) = (1, 3), (4, 5), (2, 6), (6, 7): how many rooms?

By arrival: 1–3 opens room 1, 2–6 opens room 2, 4–5 reuses room 1 (3 < 4), and 6–7 reuses room 1 again (5 < 6).

DRILL 02 · RECALL

In Room Allocation, why is the top reused only when its departure < arrival?

A guest leaving on day 5 still uses the room on day 5, so a guest arriving on day 5 needs another.

INVARIANT · INTERVALS · SORT THE ENDS, SWEEP THE LINE · INTERVALS
27 / PROBLEM #09 · HEAP · MED

Room Allocation

MED heap ▶ SOLVE ON CSESCSES does not rate its problems; the chip is this deck's estimate. Submit the Python tab as PyPy3.
SIGNAL — WHAT GIVES IT AWAY

Customers stay from day a to day b, and two may share a room only if one leaves before the other arrives. Use the fewest rooms, and say which customer gets which.

INTUITION

Take customers in order of arrival and keep a min-heap of (departure, room) for the rooms in use. If the room that frees first is free before this arrival, reuse it; if even that one is still busy, every room is, so open a new one. A new room opens only when every open room is occupied on this arrival day, so the count is the most overlapping stays, and no allocation can use fewer.

STEPS
  1. Sort the customers by arrival, keeping their input index
  2. If the heap's earliest departure is before this arrival, pop that room and reuse it
  3. Otherwise open room number size + 1
  4. Push (departure, room); print the heap's size and each customer's room
BRUTEO(kⁿ) trying every way to give n customers k rooms
→
OPTIMALO(n log n)
↕ SCROLL
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> P;
int main() {
    int n; scanf("%d", &n);
    vector<array<int, 3>> c(n);                // (arrival, departure, index)
    for (int i = 0; i < n; i++) { scanf("%d %d", &c[i][0], &c[i][1]); c[i][2] = i; }
    sort(c.begin(), c.end());                  // by arrival
    priority_queue<P, vector<P>, greater<P>> pq;   // (departure, room), the earliest on top
    vector<int> room(n);
    for (auto& x : c) {
        int r;
        if (!pq.empty() && pq.top().first < x[0]) { r = pq.top().second; pq.pop(); }   // free by now
        else r = pq.size() + 1;                // every room is busy: open one
        room[x[2]] = r;
        pq.push(P(x[1], r));
    }
    printf("%d\n", (int)pq.size());
    for (int i = 0; i < n; i++) printf("%d ", room[i]);
    printf("\n");
}
TIMEO(n log n)a sort and n heap operations
SPACEO(n)the heap and the rooms
TRAP

Sharing a room on the changeover day. The first guest must leave before the next arrives, so the test is departure < arrival. With ≤, the sample's (1, 2) and (2, 4) share a room, and the answer comes out 1.

INVARIANT · INTERVALS · SORT THE ENDS, SWEEP THE LINE · INTERVALS
28 / PROBLEM #10 · HEAP · HARD

Meeting Rooms III

HARD heap ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

n rooms; each meeting takes the lowest-numbered free room, or waits for the first room to free and keeps its length. Which room holds the most meetings?

INTUITION

Two heaps answer the two questions the rules ask. A min-heap of free room numbers gives the lowest free room. A min-heap of (end, room) for busy rooms says which frees first, and on a tie the lower room. Before each meeting, rooms done by its start move back to the free heap. With none free, the meeting takes the first room to free and is pushed back to start when that room ends.

STEPS
  1. Sort the meetings by start; push every room into free
  2. Move each busy room ending by s back into free
  3. Take the lowest free room, which ends at e
  4. With none free, pop the earliest (t, room) and end at t + (e − s); count the room
BRUTEO(m · n) simulating with a scan of every room per meeting
→
OPTIMALO(m log m + m log n)
↕ SCROLL
int mostBooked(int n, vector<vector<int>>& meetings) {
    sort(meetings.begin(), meetings.end());    // by start; the starts are distinct
    priority_queue<int, vector<int>, greater<int>> freeRooms;
    for (int r = 0; r < n; r++) freeRooms.push(r);
    typedef pair<long long, int> E;            // (end, room)
    priority_queue<E, vector<E>, greater<E>> busy;
    vector<int> cnt(n);
    for (auto& m : meetings) {
        long long s = m[0], len = m[1] - m[0];
        while (!busy.empty() && busy.top().first <= s) {   // done by the time it starts
            freeRooms.push(busy.top().second); busy.pop();
        }
        int r; long long end;
        if (!freeRooms.empty()) { r = freeRooms.top(); freeRooms.pop(); end = s + len; }
        else { r = busy.top().second; end = busy.top().first + len; busy.pop(); }   // wait for it
        cnt[r]++;
        busy.push(E(end, r));
    }
    return max_element(cnt.begin(), cnt.end()) - cnt.begin();   // the lowest room on a tie
}
TIMEO(m log m + m log n)a sort and a few heap operations per meeting
SPACEO(n)the two heaps and the counts
TRAP

Ends kept in 32 bits. Waiting meetings pile up: 10⁵ meetings of length 5·10⁵ on one room end near 5·10¹⁰, past 2³¹. Keep end times in long long or long.

INVARIANT · INTERVALS · SORT THE ENDS, SWEEP THE LINE · INTERVALS
29 / DRILL UNIT 06 · Which Room Frees First · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

mostBooked(2, [[0, 5], [1, 2], [3, 4], [6, 7]])?

Room 0 takes [0, 5) and room 1 [1, 2). Room 1 is free again for [3, 4). By 6 both are free and room 0, the lower, takes [6, 7). Two each: the tie goes to room 0.

INVARIANT · INTERVALS · SORT THE ENDS, SWEEP THE LINE · INTERVALS
30 / MECHANISM UNIT 07 · ADD AT THE START, SUBTRACT AT THE END

ADD AT THE START, SUBTRACT AT THE END

A trip adds k riders at from and removes them at to. Write both into a difference array; its running sum is the load after each stop.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · INTERVALS · SORT THE ENDS, SWEEP THE LINE · INTERVALS
31 / DRILL UNIT 07 · Add at the Start, Subtract at the End

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

carPooling([[2, 1, 4], [3, 4, 6], [2, 2, 5]], 4)?

After stop 4 the first trip's 2 are off and 3 get on, so 2 + 2 − 2 + 3 = 5 riders, more than 4.

DRILL 02 · RECALL

Why subtract at diff[to] and not at diff[to + 1]?

A trip from 1 to 5 carries its riders on stops 1 to 4 only. A trip starting at 5 never shares the car with it.

INVARIANT · INTERVALS · SORT THE ENDS, SWEEP THE LINE · INTERVALS
32 / PROBLEM #11 · COUNT · MED

Car Pooling

MED count ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Trips pick up k passengers at from and drop them at to, along one road. Can a car with this capacity take them all?

INTUITION

Riders change only at stops, and a trip adds k at from and removes k at to. Write +k at from and −k at to in a difference array. Its running sum is the load after each stop, and the car is fine if that never passes the capacity. Riders leave at to before others board there, which the −k at to already says.

STEPS
  1. diff[from] += k and diff[to] −= k for each trip
  2. load = 0
  3. For each stop s in order: load += diff[s]
  4. Return false if load ever passes capacity, else true
BRUTEO(n · S) adding every trip's riders to every stop it covers
→
OPTIMALO(n + S)
↕ SCROLL
bool carPooling(vector<vector<int>>& trips, int capacity) {
    int diff[1001] = {};                       // riders getting on minus off at each stop
    for (auto& t : trips) {
        diff[t[1]] += t[0];                    // they board at from
        diff[t[2]] -= t[0];                    // and are off by to
    }
    int load = 0;
    for (int s = 0; s <= 1000; s++) {
        load += diff[s];                       // riders after stop s
        if (load > capacity) return false;
    }
    return true;
}
TIMEO(n + S)n trips, then S = 1001 stops
SPACEO(S)the difference array
TRAP

Dropping riders at to + 1. They are off at to, so a trip ending at 5 and one starting at 5 never share the car. Subtracting at to + 1 counts both at stop 5 and turns some trues into false.

INVARIANT · INTERVALS · SORT THE ENDS, SWEEP THE LINE · INTERVALS
33 / MECHANISM UNIT 08 · ONLY THE NEIGHBOURS CAN CLASH

ONLY THE NEIGHBOURS CAN CLASH

The bookings never overlap, so sorted by start they are sorted by end too. A new one can only clash with the first booking at or after it and the one just before.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · INTERVALS · SORT THE ENDS, SWEEP THE LINE · INTERVALS
34 / DRILL UNIT 08 · Only the Neighbours Can Clash

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

book(5, 10), book(10, 15), book(8, 12)?

[5, 10) and [10, 15) touch, which half-open intervals allow. [8, 12) starts before 10 and clashes with [5, 10).

DRILL 02 · RECALL

Why is it enough to check only the two neighbours of the new booking?

Sorted by start, non-overlapping bookings are sorted by end too. Anything further away ends before the one before it, or starts after the next one.

INVARIANT · INTERVALS · SORT THE ENDS, SWEEP THE LINE · INTERVALS
35 / PROBLEM #12 · SEARCH · MED

My Calendar I

MED search ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Book half-open intervals [start, end) one by one, refusing any that would overlap a booking already made.

INTUITION

The bookings never overlap, so sorted by start they are also sorted by end. A new booking can only clash with its two neighbours in that order, the first booking starting at or after it and the one just before. Check both and insert. A sorted map gives each in O(log n).

STEPS
  1. Find the first booking starting at or after start
  2. If it starts before end, refuse
  3. If the booking before it ends after start, refuse
  4. Otherwise insert start → end and accept
BRUTEO(n) per book, checking every booking made so far
→
OPTIMALO(log n) per book
↕ SCROLL
class MyCalendar {
    map<int, int> booked;                      // start -> end, never overlapping
public:
    MyCalendar() {}
    bool book(int startTime, int endTime) {
        auto it = booked.lower_bound(startTime);   // the first one starting at or after it
        if (it != booked.end() && it->first < endTime) return false;          // starts too soon
        if (it != booked.begin() && prev(it)->second > startTime) return false;   // runs too late
        booked[startTime] = endTime;
        return true;
    }
};
TIMEO(log n) per booktwo neighbours in a sorted map (Python: O(n) to insert into a list)
SPACEO(n)the bookings
TRAP

Treating the end as booked. [10, 20) frees the room at 20, so [20, 30) fits. Testing end ≥ start refuses every booking that begins as another ends.

INVARIANT · INTERVALS · SORT THE ENDS, SWEEP THE LINE · INTERVALS
36 / MECHANISM UNIT 09 · ATTEND THE ONE THAT ENDS FIRST

ATTEND THE ONE THAT ENDS FIRST

Walk the days. Events open into a min-heap of end days on their start day, ended ones are popped and lost, and each day the event ending first is attended.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · INTERVALS · SORT THE ENDS, SWEEP THE LINE · INTERVALS
37 / DRILL UNIT 09 · Attend the One That Ends First

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

maxEvents([[1, 1], [1, 2], [1, 2], [2, 2]])?

Day 1: attend [1, 1]. Day 2: attend one of the events ending on day 2. By day 3 the other two have ended.

DRILL 02 · RECALL

Why attend the open event that ends first?

Any plan attending something else today can swap in the event that ends first, which has the fewest days left, and attend the other on its day instead.

INVARIANT · INTERVALS · SORT THE ENDS, SWEEP THE LINE · INTERVALS
38 / PROBLEM #13 · HEAP · MED

Maximum Number of Events That Can Be Attended

MED heap ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Events run from startDay to endDay, inclusive. Attend one event a day; how many events can you attend?

INTUITION

Walk the days in order. Each day, every event that has started and not ended is a candidate. Attend the one that ends first: any plan attending a different candidate today can swap it for this one, which would expire sooner. A min-heap of end days holds the candidates; events open into it on their start day, and events already over are popped and lost.

STEPS
  1. Sort by start day
  2. Each day d, push the end day of every event starting on d
  3. Pop the end days below d: those events are over
  4. If any remain, attend the one ending first: pop it and count it
BRUTEO(n! · n) trying every order of the events
→
OPTIMALO(n log n + D)
↕ SCROLL
int maxEvents(vector<vector<int>>& events) {
    sort(events.begin(), events.end());        // by start day
    priority_queue<int, vector<int>, greater<int>> ends;   // last days of the open events
    int i = 0, n = events.size(), cnt = 0;
    for (int d = 1; i < n || !ends.empty(); d++) {
        while (i < n && events[i][0] == d) ends.push(events[i++][1]);   // they open today
        while (!ends.empty() && ends.top() < d) ends.pop();            // already over
        if (!ends.empty()) { ends.pop(); cnt++; }                     // attend the one ending first
    }
    return cnt;
}
TIMEO(n log n + D)a sort, n pushes and pops, and D days
SPACEO(n)the heap
TRAP

Attending an event after its last day. The heap still holds events that ended earlier. Pop every end below d before choosing, or [[1, 1], [1, 1], [1, 1]] counts three instead of one.

INVARIANT · INTERVALS · SORT THE ENDS, SWEEP THE LINE · INTERVALS
39 / MECHANISM UNIT 10 · TAKE IT OR SKIP IT

SKIP IT, OR TAKE IT AFTER WHAT FITS

Sorted by end, the jobs that can come before job i are a prefix. dp[i + 1] is the better of skipping it, dp[i], and taking it after that prefix, found by binary search.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · INTERVALS · SORT THE ENDS, SWEEP THE LINE · INTERVALS
40 / DRILL UNIT 10 · Take It or Skip It

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

jobScheduling([1, 2, 4], [3, 5, 6], [5, 6, 5])?

By end: 1–3 (5), 2–5 (6), 4–6 (5). The last can follow 1–3: 5 + 5 = 10 beats 6. 2–5 overlaps both others.

DRILL 02 · RECALL

Why upper_bound, counting ends ≤ start, and not lower_bound?

A job may start when another ends, so a job ending exactly at the start belongs in the prefix it can follow.

INVARIANT · INTERVALS · SORT THE ENDS, SWEEP THE LINE · INTERVALS
41 / PROBLEM #14 · SEARCH · HARD

Maximum Profit in Job Scheduling

HARD search ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Jobs have a start, an end and a profit. Take jobs that do not overlap (one may start when another ends) for the most profit.

INTUITION

Profit breaks the greedy: the job ending first can be worth little. Sort by end and let dp[i] be the best profit using only the first i jobs. Job i is either skipped, giving dp[i], or taken after the jobs that end by its start. Those are a prefix of the sorted order, and a binary search on the ends finds how many.

STEPS
  1. Sort the jobs by end and list the ends
  2. dp[0] = 0
  3. j = how many ends are ≤ job i's start (upper_bound)
  4. dp[i + 1] = max(dp[i], dp[j] + profit); return dp[n]
BRUTEO(2ⁿ · n) trying every set of jobs
→
OPTIMALO(n log n)
↕ SCROLL
int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
    int n = startTime.size();
    vector<array<int, 3>> job(n);
    for (int i = 0; i < n; i++) job[i] = {endTime[i], startTime[i], profit[i]};
    sort(job.begin(), job.end());              // by end time
    vector<int> ends(n), dp(n + 1, 0);         // dp[i]: the best profit from the first i jobs
    for (int i = 0; i < n; i++) ends[i] = job[i][0];
    for (int i = 0; i < n; i++) {
        int j = upper_bound(ends.begin(), ends.end(), job[i][1]) - ends.begin();   // end by its start
        dp[i + 1] = max(dp[i], dp[j] + job[i][2]);   // skip it, or take it after those
    }
    return dp[n];
}
TIMEO(n log n)a sort and n binary searches
SPACEO(n)the jobs, the ends and dp
TRAP

A strict search. A job ending at 3 and one starting at 3 can both be taken, so the search counts ends ≤ start: upper_bound, bisect_right. With the strict version the first sample's 120 drops to 70.

INVARIANT · INTERVALS · SORT THE ENDS, SWEEP THE LINE · INTERVALS
42 / MECHANISM UNIT 11 · THE TALLEST STILL STANDING

THE TALLEST STILL STANDING

The outline changes only where a building rises or falls. Sweep those x and keep the heights standing; a key point is printed whenever the tallest of them changes.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · INTERVALS · SORT THE ENDS, SWEEP THE LINE · INTERVALS
43 / DRILL UNIT 11 · The Tallest Still Standing

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

getSkyline([[1, 3, 2], [2, 4, 4]])?

The 2 rises at 1 and the 4 at 2. The 2 falls at 3 under the 4, so nothing changes; the 4 falls at 4.

DRILL 02 · RECALL

At one x, why are rises read before falls?

If [0, 2, 3] ends at 2 and [2, 5, 3] starts there, reading the fall first drops the outline to 0 at 2 and prints two key points where there should be none.

INVARIANT · INTERVALS · SORT THE ENDS, SWEEP THE LINE · INTERVALS
44 / PROBLEM #15 · HEAP · HARD

The Skyline Problem

HARD heap ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Buildings are [left, right, height]. Return the key points of the skyline: each x where the outline's height changes, and the new height.

INTUITION

The outline can only change where a building rises or falls. Sweep those x in order and keep the heights standing now. After each event the outline's height is the tallest of them, and a key point is printed when it differs from the last. At one x, rises come before falls and the tallest rise first, so the outline never dips or prints twice there.

STEPS
  1. Make (left, −h) and (right, h) events and sort them
  2. live = {0}, a multiset of the heights standing
  3. A rise inserts h; a fall erases one h
  4. cur = the largest in live; if cur ≠ prev, print (x, cur)
BRUTEO(X · n) reading the tallest building at every distinct x
→
OPTIMALO(n log n)
↕ SCROLL
vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
    vector<pair<int, int>> ev;                 // (x, -height) rises, (x, height) falls
    for (auto& b : buildings) {
        ev.push_back(make_pair(b[0], -b[2]));
        ev.push_back(make_pair(b[1], b[2]));
    }
    sort(ev.begin(), ev.end());                // at one x: rises first, the tallest first
    multiset<int> live = {0};                  // the heights standing now; 0 is the ground
    vector<vector<int>> out;
    int prev = 0;
    for (auto& e : ev) {
        if (e.second < 0) live.insert(-e.second);      // a building rises
        else live.erase(live.find(e.second));          // one falls
        int cur = *live.rbegin();              // the tallest still standing
        if (cur != prev) { out.push_back({e.first, cur}); prev = cur; }
    }
    return out;
}
TIMEO(n log n)sorting 2n events and a log-time set per event
SPACEO(n)the events and the set
TRAP

A building still standing at its right edge. The outline drops at x = right, so a building ending at x must be gone before the height at x is read. Keeping it one step longer misplaces every fall.

INVARIANT · INTERVALS · SORT THE ENDS, SWEEP THE LINE · INTERVALS
45 / SIGNALS WHEN YOU SEE X, REACH FOR Y

WHICH MOVE, AND WHAT GIVES IT AWAY

Eleven moves, and each has a phrase in the statement that gives it away.

ADD ONE INTERVAL TO A SORTED, DISJOINT LIST

copy what ends before, merge what overlaps, copy the rest

COPY, MERGE, COPYO(n)
KEEP THE MOST INTERVALS THAT DO NOT OVERLAP

sort by end and keep whatever starts after the last kept end

EARLIEST ENDO(n log n)
THE FEWEST POINTS THAT HIT EVERY INTERVAL

sort by end and place a point at each first end missed

POINT AT THE ENDO(n log n)
TWO SORTED LISTS OF INTERVALS

intersect the current pair, then move the one that ends first

TWO POINTERSO(m + n)
THE MOST OVERLAPPING AT ONCE, OR THE FEWEST GROUPS

a +1 at each start and a −1 at each end, swept in order

EVENT SWEEPO(n log n)
ASSIGN ROOMS AND SAY WHICH ONE

a min-heap of (end, room): reuse the one that frees first

HEAP OF ENDSO(n log n)
LOADS ADDED OVER RANGES OF A SMALL LINE

+k at the start, −k at the end, then a running sum

DIFFERENCE ARRAYO(n + S)
BOOK INTERVALS ONLINE, REFUSING CLASHES

a sorted map: check the next booking and the one before

SORTED MAPO(log n)
ONE ITEM A DAY FROM WHAT IS OPEN

sweep the days with a min-heap of end days

SWEEP AND HEAPO(n log n)
INTERVALS WITH WEIGHTS TO MAXIMISE

sort by end; skip it or take it after a binary search

DP ON ENDSO(n log n)
THE OUTLINE OF OVERLAPPING RECTANGLES

sweep rises and falls with a set of heights standing

SET OF HEIGHTSO(n log n)
INVARIANT · INTERVALS · SORT THE ENDS, SWEEP THE LINE · INTERVALS
46 / RECALL RETRIEVAL, NOT RECOGNITION · 1 OF 2

NAME THE MOVE FROM THE STATEMENT

DRILL 01 · TRANSFER

Merge Intervals: merge every overlapping pair in an unsorted list. Which move?

Sort by start. Each interval either overlaps the last merged one and stretches it, or starts a new one. It is unit 1's merge, run for every interval, and the problem is Merge Intervals (arrays-2).

DRILL 02 · TRANSFER

Minimum Platforms: trains arrive and depart at given times. How few platforms so that no train waits? Which move?

Every train standing at one moment needs its own platform, and that many is enough. Sweep the arrivals and departures and keep the largest count, as in Restaurant Customers.

INVARIANT · INTERVALS · SORT THE ENDS, SWEEP THE LINE · INTERVALS
47 / RECALL RETRIEVAL, NOT RECOGNITION · 2 OF 2

NAME THE MOVE FROM THE STATEMENT

DRILL 01 · TRANSFER

N Meetings in One Room asks for the most meetings one room can hold, one at a time. Which move?

Sort by end and take every meeting that starts after the last one taken ends. It is Movie Festival under another name; check whether touching is allowed.

DRILL 02 · RECALL

When does the end-first greedy stop working, so that a dp over the ends is needed?

With equal weights, keeping the one that ends first is always safe. With profits, a short early job can be worth less than the long one it blocks, so each job is weighed. Skip it, or take it after the jobs that fit.

INVARIANT · INTERVALS · SORT THE ENDS, SWEEP THE LINE · INTERVALS
48 / TRAPS PLAUSIBLE, WRONG, AND SILENT

SIX WAYS TO BE PLAUSIBLY WRONG

None of these fail the samples. Each one fails a hidden test.

CLOSED OR HALF-OPEN?

Insert Interval, the arrows and Segments are closed, so touching intervals overlap. Non-overlapping Intervals, Movie Festival, My Calendar and Car Pooling are half-open: touching is fine. Read which before choosing < or ≤.

SORTING BY START FOR A GREEDY PICK

The interval that starts first can be the longest. Keeping and shooting both sort by end, because the earliest end leaves the most room.

A COMPARATOR THAT SUBTRACTS

a[1] − b[1] overflows when ends span −2³¹ to 2³¹ − 1. Compare instead of subtracting.

INCLUSIVE ENDS IN A SWEEP

An interval [l, r] that includes r closes at r + 1. At one time, decide whether a close sorts before an open, and make the sort say so.

A HEAP THAT STILL HOLDS THE PAST

Events that ended, rooms that freed and buildings that fell sit in a heap until popped. Clear them before reading the top.

OVERFLOW IN DELAYED ENDS

Meeting Rooms III pushes waiting meetings later and later, past 2³¹. Keep end times in 64-bit integers.

INVARIANT · INTERVALS · SORT THE ENDS, SWEEP THE LINE · INTERVALS
49 / CHEATSHEET REVISION SURFACE

ONE SCREEN, THE WHOLE DECK

Eleven moves on one page. The right column is the cue for each.

ALGORITHM
TIME
SPACE
REACH FOR IT WHEN
Copy, merge, copy
O(n)
O(n)
merge while start ≤ hi; stretch lo and hi
Earliest end
O(n log n)
O(1)
sort by end; keep if start ≥ last end
Point at the end
O(n log n)
O(1)
sort by end; new point at end if start > point
Two pointers
O(m + n)
O(1)
[max start, min end]; move the earlier end
Event sweep
O(n log n)
O(n)
+1 at start, −1 at end (r + 1 if inclusive)
Heap of ends
O(n log n)
O(n)
reuse the top if it frees before the arrival
Two heaps
O(m log n)
O(n)
free rooms by number, busy rooms by (end, room)
Difference array
O(n + S)
O(S)
diff[from] += k, diff[to] −= k, running sum
Sorted map
O(log n)
O(n)
check lower_bound and the entry before it
Sweep and heap
O(n log n)
O(n)
push today's ends, pop the past, take the top
DP on ends
O(n log n)
O(n)
dp[i+1] = max(dp[i], dp[upper_bound(start)] + p)
INVARIANT · INTERVALS · SORT THE ENDS, SWEEP THE LINE · INTERVALS
50 / CLOSE MODULE 22 · INTERVALS

TAKE IT NOW

The new interval swallowed what it overlapped; the earliest end was kept, and an arrow flew at each first end missed; two pointers walked two sorted lists; a +1 and a −1 per interval counted what was open; a heap of departures said which room freed first, and a second heap kept the free ones; a difference array carried the riders; a sorted map checked only the neighbours; the event ending first was attended; profit turned the greedy into a dp over the ends; and a set of heights traced the skyline. Merge Intervals is unit 1's merge, run for every interval, in arrays-2.

00%
OF THIS DECK SOLVED
← ALL TOPICS← GREEDYHEAPS →

Module 22. Fifteen problems: eleven on LeetCode, three on CSES and one on Codeforces. Next in the sheet: graph traversal.

INVARIANT · INTERVALS · SORT THE ENDS, SWEEP THE LINE · INTERVALS
■ TOO SMALL TO READ
1280×720
INVARIANT · MODULE 22 · INTERVALS

This one needs a laptop

Not a preference — an arithmetic one. Every slide is a fixed 1280 × 720 stage: a graph animating beside the code that drives it, with the problems laid out two columns wide. It scales as a single piece, so on a screen this size the body text comes out around 4px tall.

Shrinking it further would not help, and rebuilding it to reflow would mean losing the thing that makes it worth reading.

YOUR SCREEN0 × 0
NEEDED1060 × 610
WHAT IS WAITING ON THE LAPTOP
WATCH IT RUN, THEN RUN IT FROM MEMORY
Your progress is saved per device, so anything you tick on the laptop will be waiting there.