Many companies provide their employees time-limited DoorDash credits as perks.
Each credit:
- Has a time window when it can be used
- Has a credit amount
A customer placing one order can combine multiple credits, as long as their time windows overlap with the order time.
You are given a list of credits, each represented as:
["START–END", "CREDIT"]
Your task is to determine the maximum credit amount the customer can use at any valid time, by finding the maximum sum of all credits whose intervals overlap.
Return the maximum total credit that can be applied at the same time.
Example 1
[["10:00–11:00", "5"], ["13:00–15:00", "10"]]
Output:
10
Explanation:
The intervals do not overlap.
The maximum credit available at any single time window is simply the largest one → 10.
这题本质是：
找出一天中任意一个时间点，最多能叠多少信用额度（credit）。
每个 credit 都有一个可使用时间段：
✅ 时间段重叠 → 可以叠加
❌ 不重叠 → 不能一起用
最后返回 重叠区间中“额度之和”最大的那个值 。
✅ 面试官希望你做到这一点：
1) 正确解析时间
把“10:00–11:00”转成分钟区间：
600–660
这样区间就能排序、比较。
2) 使用“扫描线 Sweep Line”
每个 credit 变成两个事件：
start → +credit
end → –credit
对所有事件排序后，从早到晚扫一遍：
- current_sum += credit
- max_sum = max(max_sum, current_sum)
3) 避免 O(n²)
直接两两比重叠是新手写法，会超时。
DoorDash VO 期望你用 O(n log n) 的扫描线。
4) 清晰表达“重叠区间 = 可叠加 credit”
只要区间有交集，就能叠加。
面试官最关心你是否能：
- 把时间标准化
- 抽象为“区间重叠加权”问题
- 用扫描线找到最大同时活跃额度
- 讲得简单清楚
VOprep 团队长期陪同学员实战各类大厂 OA 与 VO，包括 Doordash、Google、Amazon、Citadel、SIG 等，提供实时答案助攻、远程陪练与面试节奏提醒，帮助大家在关键时刻不卡壳。
如果你也在准备 Tiktok 或类似工程向公司，可以了解一下我们的定制助攻方案——从编程面到系统设计，全程护航上岸。
