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.
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.
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.
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.
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.
A list of intervals, sorted and disjoint, gets one more. Insert it and merge whatever it overlaps.
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.
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; }
public int[][] insert(int[][] intervals, int[] newInterval) { List<int[]> out = new ArrayList<>(); int i = 0, n = intervals.length; int lo = newInterval[0], hi = newInterval[1]; while (i < n && intervals[i][1] < lo) out.add(intervals[i++]); // ends before it starts while (i < n && intervals[i][0] <= hi) { // overlaps it: merge lo = Math.min(lo, intervals[i][0]); hi = Math.max(hi, intervals[i][1]); i++; } out.add(new int[]{lo, hi}); while (i < n) out.add(intervals[i++]); // starts after it ends return out.toArray(new int[0][]); }
def insert(intervals, newInterval): out, i, n = [], 0, len(intervals) lo, hi = newInterval while i < n and intervals[i][1] < lo: # ends before it starts out.append(intervals[i]) i += 1 while i < n and intervals[i][0] <= hi: # overlaps it: merge lo = min(lo, intervals[i][0]) hi = max(hi, intervals[i][1]) i += 1 out.append([lo, hi]) out.extend(intervals[i:]) # starts after it ends return out
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.
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.
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.
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.
Remove the fewest intervals so that the rest do not overlap. Touching at an endpoint is allowed.
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.
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; }
public int eraseOverlapIntervals(int[][] intervals) { Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1])); // by end int kept = 0, end = Integer.MIN_VALUE; for (int[] v : intervals) if (v[0] >= end) { kept++; end = v[1]; } // starts once the last kept one ends return intervals.length - kept; }
def eraseOverlapIntervals(intervals): intervals.sort(key=lambda v: v[1]) # by end kept, end = 0, float("-inf") for s, e in intervals: if s >= end: # starts once the last kept one ends kept += 1 end = e return len(intervals) - kept
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.
Movies have start and end times. Watch the most movies entirely; one may start the moment another ends.
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.
#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); }
import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); in.nextToken(); int n = (int) in.nval; int[][] m = new int[n][2]; for (int i = 0; i < n; i++) { in.nextToken(); m[i][0] = (int) in.nval; in.nextToken(); m[i][1] = (int) in.nval; } Arrays.sort(m, (x, y) -> Integer.compare(x[1], y[1])); // the earliest end first int cnt = 0, end = 0; for (int[] v : m) if (v[0] >= end) { cnt++; end = v[1]; } // it starts once the last one ends System.out.println(cnt); } }
import sys def main(): data = sys.stdin.buffer.read().split() n = int(data[0]) a = map(int, data[1:2 * n + 1:2]) b = map(int, data[2:2 * n + 2:2]) cnt, end = 0, 0 for e, s in sorted(zip(b, a)): # (end, start), the earliest end first if s >= end: # it starts once the last one ends cnt += 1 end = e print(cnt) main()
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.
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.
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.
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.
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.
Balloons span [start, end] along a line. An arrow at x bursts every balloon covering x. Burst them all with the fewest arrows.
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.
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; }
public int findMinArrowShots(int[][] points) { Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1])); // by end, no subtraction int arrows = 0; long at = Long.MIN_VALUE; // where the last arrow flew for (int[] p : points) if (p[0] > at) { arrows++; at = p[1]; } // missed it: shoot at its end return arrows; }
def findMinArrowShots(points): points.sort(key=lambda p: p[1]) # by end arrows, at = 0, float("-inf") # where the last arrow flew for s, e in points: if s > at: # missed it: shoot at its end arrows += 1 at = e return arrows
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++.
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.
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.
#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"); }
import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); in.nextToken(); int n = (int) in.nval; int[][] s = new int[n][2]; // (right, left) for (int i = 0; i < n; i++) { in.nextToken(); int a = (int) in.nval; in.nextToken(); int b = (int) in.nval; s[i][0] = Math.max(a, b); s[i][1] = Math.min(a, b); // the ends may come in either order } Arrays.sort(s, (x, y) -> x[0] != y[0] ? Integer.compare(x[0], y[0]) : Integer.compare(x[1], y[1])); List<Integer> nails = new ArrayList<>(); for (int[] p : s) if (nails.isEmpty() || p[1] > nails.get(nails.size() - 1)) // not nailed yet nails.add(p[0]); // nail it at its right end StringBuilder out = new StringBuilder(); out.append(nails.size()).append('\n'); for (int x : nails) out.append(x).append(' '); System.out.println(out.toString().trim()); } }
import sys def main(): data = list(map(int, sys.stdin.buffer.read().split())) n = data[0] segs = [] for i in range(n): a, b = data[1 + 2 * i], data[2 + 2 * i] segs.append((max(a, b), min(a, b))) # the ends may come in either order segs.sort() # the earliest right end first nails = [] for r, l in segs: if not nails or l > nails[-1]: # not nailed yet nails.append(r) # nail it at its right end print(len(nails)) print(*nails) main()
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.
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.
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.
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].
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.
Two lists of closed intervals, each sorted and disjoint. Return every intersection of an interval in one with an interval in the other.
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.
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; }
public int[][] intervalIntersection(int[][] firstList, int[][] secondList) { List<int[]> out = new ArrayList<>(); int i = 0, j = 0; while (i < firstList.length && j < secondList.length) { int lo = Math.max(firstList[i][0], secondList[j][0]); // the later start int hi = Math.min(firstList[i][1], secondList[j][1]); // the earlier end if (lo <= hi) out.add(new int[]{lo, hi}); if (firstList[i][1] < secondList[j][1]) i++; // the one that ends first is done else j++; } return out.toArray(new int[0][]); }
def intervalIntersection(firstList, secondList): out, i, j = [], 0, 0 while i < len(firstList) and j < len(secondList): lo = max(firstList[i][0], secondList[j][0]) # the later start hi = min(firstList[i][1], secondList[j][1]) # the earlier end if lo <= hi: out.append([lo, hi]) if firstList[i][1] < secondList[j][1]: # the one that ends first is done i += 1 else: j += 1 return out
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.
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.
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.
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.
Customers arrive and leave at distinct times. What is the most customers in the restaurant at once?
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.
#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); }
import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); in.nextToken(); int n = (int) in.nval; long[] ev = new long[2 * n]; // time * 2 + 1 arrives, time * 2 leaves for (int i = 0; i < n; i++) { in.nextToken(); ev[2 * i] = (long) in.nval * 2 + 1; in.nextToken(); ev[2 * i + 1] = (long) in.nval * 2; } Arrays.sort(ev); // every time is distinct int cur = 0, best = 0; for (long e : ev) { cur += (e & 1) == 1 ? 1 : -1; // one more customer, or one fewer best = Math.max(best, cur); } System.out.println(best); } }
import sys def main(): data = sys.stdin.buffer.read().split() n = int(data[0]) ev = [] for i in range(n): ev.append((int(data[1 + 2 * i]), 1)) # arrives ev.append((int(data[2 + 2 * i]), -1)) # leaves ev.sort() # every time is distinct cur = best = 0 for t, d in ev: cur += d # one more customer, or one fewer best = max(best, cur) print(best) main()
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.
Split inclusive intervals into the fewest groups so that no two in a group intersect; [1, 5] and [5, 8] do.
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.
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; }
public int minGroups(int[][] intervals) { int n = intervals.length; long[] ev = new long[2 * n]; // time * 2 + 1 opens, time * 2 closes for (int i = 0; i < n; i++) { ev[2 * i] = (long) intervals[i][0] * 2 + 1; ev[2 * i + 1] = (long) (intervals[i][1] + 1) * 2; } Arrays.sort(ev); // at one time, a close sorts before an open int cur = 0, best = 0; for (long e : ev) { cur += (e & 1) == 1 ? 1 : -1; best = Math.max(best, cur); // the most open at once } return best; }
def minGroups(intervals): ev = [] for l, r in intervals: ev.append((l, 1)) # it opens at left ev.append((r + 1, -1)) # and is closed from right + 1 on ev.sort() # at one time, -1 sorts before +1 cur = best = 0 for t, d in ev: cur += d best = max(best, cur) # the most open at once return best
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.
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]}.
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.
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.
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).
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.
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.
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.
#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"); }
import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); in.nextToken(); int n = (int) in.nval; int[][] c = new int[n][3]; // (arrival, departure, index) for (int i = 0; i < n; i++) { in.nextToken(); c[i][0] = (int) in.nval; in.nextToken(); c[i][1] = (int) in.nval; c[i][2] = i; } Arrays.sort(c, (x, y) -> x[0] != y[0] ? Integer.compare(x[0], y[0]) : x[1] != y[1] ? Integer.compare(x[1], y[1]) : Integer.compare(x[2], y[2])); PriorityQueue<int[]> pq = new PriorityQueue<>((x, y) -> x[0] != y[0] ? Integer.compare(x[0], y[0]) : Integer.compare(x[1], y[1])); // (departure, room) int[] room = new int[n]; for (int[] x : c) { int r; if (!pq.isEmpty() && pq.peek()[0] < x[0]) r = pq.poll()[1]; // free by now else r = pq.size() + 1; // every room is busy: open one room[x[2]] = r; pq.add(new int[]{x[1], r}); } StringBuilder out = new StringBuilder(); out.append(pq.size()).append('\n'); for (int i = 0; i < n; i++) out.append(room[i]).append(' '); System.out.println(out.toString().trim()); } }
import sys, heapq def main(): data = list(map(int, sys.stdin.buffer.read().split())) n = data[0] c = sorted((data[1 + 2 * i], data[2 + 2 * i], i) for i in range(n)) # by arrival pq, room = [], [0] * n # pq: (departure, room), the earliest on top for a, b, i in c: if pq and pq[0][0] < a: # the room that frees first is free by now r = heapq.heappop(pq)[1] else: r = len(pq) + 1 # every room is busy: open one room[i] = r heapq.heappush(pq, (b, r)) print(len(pq)) print(*room) main()
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.
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?
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.
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 }
public int mostBooked(int n, int[][] meetings) { Arrays.sort(meetings, (a, b) -> Integer.compare(a[0], b[0])); // by start; distinct PriorityQueue<Integer> free = new PriorityQueue<>(); for (int r = 0; r < n; r++) free.add(r); PriorityQueue<long[]> busy = new PriorityQueue<>((a, b) -> a[0] != b[0] ? Long.compare(a[0], b[0]) : Long.compare(a[1], b[1])); // (end, room) int[] cnt = new int[n]; for (int[] m : meetings) { long s = m[0], len = m[1] - m[0]; while (!busy.isEmpty() && busy.peek()[0] <= s) free.add((int) busy.poll()[1]); // done by s int r; long end; if (!free.isEmpty()) { r = free.poll(); end = s + len; } else { long[] t = busy.poll(); r = (int) t[1]; end = t[0] + len; } // wait for it cnt[r]++; busy.add(new long[]{end, r}); } int best = 0; for (int r = 1; r < n; r++) if (cnt[r] > cnt[best]) best = r; // the lowest room on a tie return best; }
import heapq def mostBooked(n, meetings): meetings.sort() # by start; the starts are distinct free = list(range(n)) # a min-heap of room numbers busy = [] # (end, room) cnt = [0] * n for s, e in meetings: while busy and busy[0][0] <= s: # done by the time it starts heapq.heappush(free, heapq.heappop(busy)[1]) if free: r = heapq.heappop(free) end = e else: t, r = heapq.heappop(busy) # wait for the first room to free end = t + (e - s) # the same length, starting at t cnt[r] += 1 heapq.heappush(busy, (end, r)) return cnt.index(max(cnt)) # the lowest room on a tie
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.
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.
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.
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.
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.
Trips pick up k passengers at from and drop them at to, along one road. Can a car with this capacity take them all?
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.
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; }
public boolean carPooling(int[][] trips, int capacity) { int[] diff = new int[1001]; // riders getting on minus off at each stop for (int[] 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; }
def carPooling(trips, capacity): diff = [0] * 1001 # riders getting on minus off at each stop for k, a, b in trips: diff[a] += k # they board at from diff[b] -= k # and are off by to load = 0 for s in range(1001): load += diff[s] # riders after stop s if load > capacity: return False return True
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.
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.
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).
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.
Book half-open intervals [start, end) one by one, refusing any that would overlap a booking already made.
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).
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; } };
class MyCalendar { TreeMap<Integer, Integer> booked = new TreeMap<>(); // start -> end, never overlapping public MyCalendar() {} public boolean book(int startTime, int endTime) { Integer next = booked.ceilingKey(startTime); // the first one starting at or after it if (next != null && next < endTime) return false; Map.Entry<Integer, Integer> before = booked.lowerEntry(startTime); if (before != null && before.getValue() > startTime) return false; booked.put(startTime, endTime); return true; } }
import bisect class MyCalendar: def __init__(self): self.starts, self.ends = [], [] # sorted by start, never overlapping def book(self, startTime, endTime): i = bisect.bisect_left(self.starts, startTime) # the first one starting at or after it if i < len(self.starts) and self.starts[i] < endTime: return False # it starts before this one ends if i > 0 and self.ends[i - 1] > startTime: return False # the one before runs past this start self.starts.insert(i, startTime) self.ends.insert(i, endTime) return True
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.
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.
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.
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.
Events run from startDay to endDay, inclusive. Attend one event a day; how many events can you attend?
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.
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; }
public int maxEvents(int[][] events) { Arrays.sort(events, (a, b) -> Integer.compare(a[0], b[0])); // by start day PriorityQueue<Integer> ends = new PriorityQueue<>(); // last days of the open events int i = 0, n = events.length, cnt = 0; for (int d = 1; i < n || !ends.isEmpty(); d++) { while (i < n && events[i][0] == d) ends.add(events[i++][1]); // they open today while (!ends.isEmpty() && ends.peek() < d) ends.poll(); // already over if (!ends.isEmpty()) { ends.poll(); cnt++; } // attend the one ending first } return cnt; }
import heapq def maxEvents(events): events.sort() # by start day ends, i, n, cnt, d = [], 0, len(events), 0, 0 while i < n or ends: d += 1 while i < n and events[i][0] == d: # they open today heapq.heappush(ends, events[i][1]) i += 1 while ends and ends[0] < d: # already over heapq.heappop(ends) if ends: # attend the one ending first heapq.heappop(ends) cnt += 1 return cnt
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.
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.
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.
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.
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.
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.
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]; }
public int jobScheduling(int[] startTime, int[] endTime, int[] profit) { int n = startTime.length; int[][] job = new int[n][]; for (int i = 0; i < n; i++) job[i] = new int[]{endTime[i], startTime[i], profit[i]}; Arrays.sort(job, (a, b) -> Integer.compare(a[0], b[0])); // by end time int[] dp = new int[n + 1]; // dp[i]: the best profit from the first i jobs for (int i = 0; i < n; i++) { int lo = 0, hi = i; // the first job ending after its start while (lo < hi) { int mid = (lo + hi) >>> 1; if (job[mid][0] <= job[i][1]) lo = mid + 1; else hi = mid; } dp[i + 1] = Math.max(dp[i], dp[lo] + job[i][2]); // skip it, or take it after those } return dp[n]; }
import bisect def jobScheduling(startTime, endTime, profit): job = sorted(zip(endTime, startTime, profit)) # by end time ends = [e for e, s, p in job] dp = [0] * (len(job) + 1) # dp[i]: the best profit from the first i jobs for i, (e, s, p) in enumerate(job): j = bisect.bisect_right(ends, s) # the jobs that end by its start dp[i + 1] = max(dp[i], dp[j] + p) # skip it, or take it after those return dp[-1]
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.
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.
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.
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.
Buildings are [left, right, height]. Return the key points of the skyline: each x where the outline's height changes, and the new height.
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.
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; }
public List<List<Integer>> getSkyline(int[][] buildings) { List<int[]> ev = new ArrayList<>(); // (x, -height) rises, (x, height) falls for (int[] b : buildings) { ev.add(new int[]{b[0], -b[2]}); ev.add(new int[]{b[1], b[2]}); } ev.sort((a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0]) : Integer.compare(a[1], b[1])); TreeMap<Integer, Integer> live = new TreeMap<>(); // height -> how many stand live.put(0, 1); // the ground List<List<Integer>> out = new ArrayList<>(); int prev = 0; for (int[] e : ev) { if (e[1] < 0) live.merge(-e[1], 1, Integer::sum); // a building rises else if (live.merge(e[1], -1, Integer::sum) == 0) live.remove(e[1]); // one falls int cur = live.lastKey(); // the tallest still standing if (cur != prev) { out.add(Arrays.asList(e[0], cur)); prev = cur; } } return out; }
import heapq def getSkyline(buildings): ev = [] for l, r, h in buildings: ev.append((l, -h, r)) # a rise; it stands until r ev.append((r, 0, 0)) # a fall: look again at what stands ev.sort() # at one x: rises first, the tallest first live = [(0, float("inf"))] # (-height, right end); the ground never ends out = [] for x, nh, r in ev: if nh: heapq.heappush(live, (nh, r)) # a building rises while live[0][1] <= x: # the tallest has ended: drop it heapq.heappop(live) cur = -live[0][0] # the tallest still standing if not out or out[-1][1] != cur: out.append([x, cur]) return out
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.
Eleven moves, and each has a phrase in the statement that gives it away.
copy what ends before, merge what overlaps, copy the rest
COPY, MERGE, COPYO(n)sort by end and keep whatever starts after the last kept end
EARLIEST ENDO(n log n)sort by end and place a point at each first end missed
POINT AT THE ENDO(n log n)intersect the current pair, then move the one that ends first
TWO POINTERSO(m + n)a +1 at each start and a −1 at each end, swept in order
EVENT SWEEPO(n log n)a min-heap of (end, room): reuse the one that frees first
HEAP OF ENDSO(n log n)+k at the start, −k at the end, then a running sum
DIFFERENCE ARRAYO(n + S)a sorted map: check the next booking and the one before
SORTED MAPO(log n)sweep the days with a min-heap of end days
SWEEP AND HEAPO(n log n)sort by end; skip it or take it after a binary search
DP ON ENDSO(n log n)sweep rises and falls with a set of heights standing
SET OF HEIGHTSO(n log n)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).
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.
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.
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.
None of these fail the samples. Each one fails a hidden test.
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 ≤.
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[1] − b[1] overflows when ends span −2³¹ to 2³¹ − 1. Compare instead of subtracting.
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.
Events that ended, rooms that freed and buildings that fell sit in a heap until popped. Clear them before reading the top.
Meeting Rooms III pushes waiting meetings later and later, past 2³¹. Keep end times in 64-bit integers.
Eleven moves on one page. The right column is the cue for each.
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.
Module 22. Fifteen problems: eleven on LeetCode, three on CSES and one on Codeforces. Next in the sheet: graph traversal.
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.