Analysis: Seating by Bruce Merry


Let's start by just considering how to find the location for seating arriving cows. Clearly a linear scan will be too slow, so we need some sort of data structure to accelerate these queries. Let's think about solving the query recursively: if the left half has a big enough gap then we use that, otherwise we try the gap that crosses from the left to the right half (if any), and failing that we try the right half.

Our data structure should match this recursive approach, so we use a binary tree, where the root node represents the entire range of seats and each child of a node represents the left or right half of the parent. We will need to store a few fields in each node:

  1. The biggest empty gap in the node
  2. The size of the gap adjacent to the left edge
  3. The size of the gap adjacent to the right edge

This contains all the information necessary to answer the queries in O(log N) time each.

Next, we need to consider how to apply updates: either seating the party for whom we've just found a gap, or freeing up seats in a range. The first thing to note is that the fields we store in a node can be recomputed from the corresponding fields in the two children. Thus, a simple approach to modifying a node is to make the modifications to the two children (with an early out if the range to update does not intersect both children), and then recomputing the current node. However, that will require time proportional to the length of the range, which will again be too slow. What we need is some way to quickly mark a higher-level node as completely full or completely empty, without visiting all its descendants. In fact, we do exactly that, by adding a field to each node to indicate whether it is completely full, completely empty, or other. When a node is marked completely full/empty, its descendants have undefined values and should not be consulted. When updating a node it will sometimes need to change from completely full/empty to other; in this case the full/empty status needs to be propagated to its children. The query process given above then needs to be slightly modified to process full/empty nodes directly without examining the invalid children.

With these changes, both queries and updates can be processed in O(log N) time, making the entire process O(N + M.log N) time.