Closing Time: Find the Earliest Time All Stores in a Region Can Close

Question

## Problem

You have `n` stores, each with a closing time (in minutes from midnight). A region "closes" when all stores are closed. However, stores can be forced to close early by paying a penalty of `P` dollars per minute of early closure.

Given a budget `B`, find the earliest possible region closing time. You may distribute early closure across any stores.

```python
from typing import List

def earliest_close(closing_times: List[int], P: int, B: int) -> int:
    # return the earliest achievable region closing time (in minutes)
    pass
```

**Example:**
```
closing_times = [300, 360, 420]
P = 10, B = 1000

Target T=300: need to reduce 360->300 (60 min * $10=$600) and 420->300 (120 min * $10=$1200). Total=$1800 > $1000.
Target T=330: reduce 360->330 ($300) and 420->330 ($900). Total=$1200 > $1000.
Target T=350: reduce 360->350 ($100) and 420->350 ($700). Total=$800 <= $1000.

Output: 350
```

## Approach

Binary search on target closing time T. For a given T, compute total cost = sum of `max(0, t - T) * P` for all stores. Time: O(n log(max_time)).

## Follow-ups

1. What if different stores have different per-minute penalty rates?
2. How would you find the minimum budget required to close by a given target time?
3. What if some stores cannot be forced to close early at all?
4. How does the problem change if stores also have an earliest possible open time and must remain open for a minimum duration?

Closing Time: Find the Earliest Time All Stores in a Region Can Close

Question Details

Full Details

Topics

More from Stripe