Rectangle board with remove-at-cell, batch remove and undo

Build a RectangleBoard that holds axis-aligned rectangles on a grid of width columns and height rows. Cells use zero-indexed (x, y), where x is the column and y is the row. A rectangle is given by its top-left corner (x1, y1) and bottom-right corner (x2, y2). Both corners are inclusive, so (2, 2, 2, 2) covers one cell.

Rectangles may overlap. Where several cover a cell, the one added most recently is on top. Each add gets the next ID, starting at 1. IDs are never reused, even after a rectangle is removed or an add is undone.

The interview comes in parts. Finish each part before you start the next.

Part 1. Implement:

• RectangleBoard(width, height)
• add(x1, y1, x2, y2) -> int: place a rectangle and return its ID. Raise an error if a corner is off the board or the corners are reversed.
• remove(id) -> bool: remove that rectangle. Return False if it is not on the board.
• top_at(x, y) -> int | None: the ID of the top rectangle at the cell, or None.

Part 2. remove_at(x, y) -> int | None: remove the top rectangle at the cell and return its ID, or None if the cell is empty.

Part 3. remove_many(ids) -> int: remove every listed rectangle that is on the board and return how many were removed. Ignore unknown or duplicate IDs.

Part 4. undo() -> bool: reverse the most recent operation that changed the board. Return False if there is nothing to undo. A restored rectangle comes back with its original ID, coordinates and stacking position. A batch from Part 3 is undone in one step. Operations that changed nothing are not undone.

Example. On a 6×4 board:

add(0, 0, 3, 1)   -> 1
add(2, 1, 5, 3)   -> 2
top_at(2, 1)      -> 2
remove_at(2, 1)   -> 2
top_at(2, 1)      -> 1
undo()            -> True    # rectangle 2 is back
top_at(2, 1)      -> 2
add(4, 0, 4, 0)   -> 3
remove_many([1, 3, 7]) -> 2
top_at(0, 0)      -> None
undo()            -> True    # 1 and 3 both return
top_at(4, 0)      -> 3

Constraints: the board is at most 1000×1000, and there are at most 10^4 operations. Say which operation you are optimizing for.