Stage Outline
HardIntervals
Problem
A set designer stacks rectangular flats on a stage floor. Flat i is [left, right, height]: it spans the floor from left to right and rises to height. Seen from the audience, the flats form one outline: at each position, the height of the tallest flat covering it (a flat covers [left, right)), or 0 where there is none.
Return the outline as its change points: a list of [x, h] sorted by x, where the outline height becomes h at position x. List a point only where the height actually changes, so consecutive points never share the same h. The last point always has h = 0.
Example 1
- Input:
- flats = [[1, 5, 3], [2, 4, 6]]
- Output:
- [[1, 3], [2, 6], [4, 3], [5, 0]]
The taller flat sits on top of the shorter one between 2 and 4.
Example 2
- Input:
- flats = [[0, 2, 3], [2, 5, 3]]
- Output:
- [[0, 3], [5, 0]]
Two equal-height flats side by side give a single flat top, so no point is listed at x = 2.
Constraints
- 1 ≤ flats.length ≤ 10^4
- 0 ≤ left < right ≤ 2^31 - 1
- 1 ≤ height ≤ 2^31 - 1
Hint
Show the first hint
The outline can only change at a flat's left or right edge. Consider just those x positions.
Walkthrough
How to approach it
01Clarify before coding
- Is a flat's right edge part of it? No, it covers [left, right), so at x = right the height may drop.
- Should equal heights at a joint produce a point? No, only real changes are listed.
- Is the input sorted? Not necessarily.
02Brute force
At every edge x, scan all flats for the tallest one covering x and emit a point when it changes.
Cost: O(n²) time: 2n edges times n flats, 2·10^8 for n = 10^4.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.