Doorway

The statement says “total length of horizontal intervals,” which sounds like we may need to juggle a bunch of disconnected holes. Thankfully, no. That would be gross.

If there are two neighboring common openings with blocked junk between them, we can slide the doors sitting between those openings to one side. This merges the two openings and does not decrease their total open length. Repeat this until only one opening remains.

So we only need to maximize the length of one common interval.

One Layer

Take one layer with walls $[x_1,x_2]$ and door lengths

$$l_1,l_2,\dots,l_k.$$

Let

$$pref[j]=\sum_{t=1}^{j} l_t,$$

with $pref[0]=0$, and let $S=pref[k]$ be the total door length.

Suppose the final opening is some interval $[l,r]$. In this layer, every door must be either completely left of the opening or completely right of it. Since doors cannot swap order, this is determined by a split index $j$:

• doors $1..j$ go left,
• doors $j+1..k$ go right.

For a fixed split, the best thing is obvious: shove the left doors as far left as possible and shove the right doors as far right as possible. Then the largest empty interval created by this split is

$$[x_1+pref[j],\ x_2-(S-pref[j])].$$

Equivalently:

$$[x_1+pref[j],\ x_2-S+pref[j]].$$

So each layer gives us $k+1$ candidate empty intervals, one for each split.

Global Reformulation

Now the problem is:

For every layer, choose one of its candidate intervals. Maximize the length of the intersection of all chosen intervals.

If the chosen interval for layer $i$ is $[A_i,B_i]$, the common opening length is

$$\min_i B_i - \max_i A_i.$$

If this is negative, it contributes $0$.

For one layer, as $j$ increases, both endpoints increase:

$$A_j=x_1+pref[j], \qquad B_j=x_2-S+pref[j].$$

This monotonicity is the whole trick.

Sweep

Start with split $j=0$ for every layer. That means every door is shoved to the right, and the current interval for a layer is

$$[x_1,\ x_2-S].$$

Maintain:

• maxLeft: the maximum left endpoint among currently chosen intervals,
• a multiset of all current right endpoints, so its minimum is the limiting right boundary.

Current answer candidate:

$$\minRight - maxLeft.$$

Now consider moving one more door of some layer to the left side. If we move door $j$ of a layer, that layer changes from split $j-1$ to split $j$.

The new left endpoint becomes

$$x_1+pref[j],$$

and the right endpoint changes from

$$x_2-S+pref[j-1]$$

to

$$x_2-S+pref[j].$$

Create one event for each door with exactly those values. Sort events by the new left endpoint.

When processing all events with the same left endpoint:

1. remove their old right endpoints from the multiset,
2. insert their new right endpoints,
3. update maxLeft,
4. try the current answer.

Why The Sweep Is Correct

Fix some possible final left boundary $L$.

For any layer, if another split has left endpoint at most $L$, taking that later split can only increase that layer's right endpoint and will not increase the global left boundary past $L$. So for this $L$, the best state is: apply all moves whose new left endpoint is at most $L$.

That is exactly what the sorted sweep represents. We check every coordinate where the state can change, so we don't miss the optimum.

Complexity

There is one event per door, so $O(\sum k_i)$ events.

Sorting them and doing multiset updates gives

$$O\left((n+\sum k_i)\log(n+\sum k_i)\right).$$

Memory is linear. Clean enough; no cursed geometry needed.