Checkpoint: stacks, search, and intervals
Debrief
The two adaptations that half of these needed, and what a bad result here means.
Key idea
Stacks of positions, not values
The parentheses repair problem is the one worth going back over. A stack holding characters can tell you the string is invalid; it cannot tell you which characters to delete.
Holding indexes instead solves it. Every unmatched opener is still on the stack when the scan ends, and every unmatched closer can be recorded the moment it arrives with nothing to match. Collect both sets of positions and rebuild the string skipping them.
This is the same upgrade as U4's monotonic stacks, which hold indexes precisely because the answers are about position. When a stack solution can detect a problem but not locate it, holding indexes is almost always the fix.
Key idea
Events that carry a size
The car pooling problem changes the sweep in one way: an event adds or removes several units at once rather than one. So the change stored with each event is the passenger count rather than a fixed plus or minus one.
That is a one-character change to code you already wrote, and it is the whole difficulty. Recognizing that a familiar technique needs its state widened rather than replaced is worth more than any individual pattern.
Why it works
The packet problem is the answer-space template exactly
Candidate range: the largest single item at the low end, since no cap below that can hold it, and the total at the high end, since one group always fits everything. Both defensible in a sentence.
Feasibility test: greedily fill groups up to the cap and count how many you needed. Monotonicity: a larger cap never needs more groups, so feasibility flips once and stays.
If those three did not come to you, reread U5's answer-space lesson rather than this problem. The template is the transferable thing.
Tip
What your results mean
The two interval problems wanted different techniques. If you reached for a sweep on both, or a merge on both, the gap is that you are matching on the word interval rather than on what the question asks. Merge answers questions about the shape of the union; a sweep answers questions about a moment.
If the recall half went badly but the transfer half went well, that is retention and the review queue handles it. The reverse means recognition, and the fix is the thirty-second naming habit before every problem from here on.
Why hold indexes?
In the parentheses repair, what does a stack of indexes give you that a stack of characters does not?
Sweep or merge?
Select every question that an event sweep answers better than merging the intervals.