题目描述
给定一天中的日程事件列表，实现算法返回 Busy View 时间段列表。Busy View 是将所有重叠或相邻的事件时间段合并后的结果，不显示具体事件详情。
每个事件有开始时间、结束时间和标题。时间精确到分钟。
示例
输入事件列表：
(100, 300, "Some Event") // 1:00 am 到 3:00 am
(115, 145, "Some Event")
(145, 215, "Some Event")
(200, 400, "Some Event")
(215, 230, "Some Event")
(215, 415, "Some Event")
(600, 700, "Some Event")
(500, 600, "Some Event")
输出 Busy View：
(100, 415) // 1:00 am 到 4:15 am 忙碌
(500, 700) // 5:00 am 到 7:00 am 忙碌
解题思路
这是经典的区间合并问题：
- 按开始时间对所有事件排序
- 遍历事件，如果当前事件与上一个合并后的区间重叠或相邻，则合并
- 否则开始一个新的区间
Python 实现
def get_busy_view(events: list) -> list:
if not events:
return []
# 按开始时间排序
events.sort(key=lambda x: x[0])
result = []
current_start, current_end = events[0][0], events[0][1]
for start, end, _ in events[1:]:
if start <= current_end:
# 重叠或相邻，扩展当前区间
current_end = max(current_end, end)
else:
# 不重叠，保存当前区间，开始新区间
result.append((current_start, current_end))
current_start, current_end = start, end
# 别忘了最后一个区间
result.append((current_start, current_end))
return result
# 测试
events = [
(100, 300, "Event1"),
(115, 145, "Event2"),
(145, 215, "Event3"),
(200, 400, "Event4"),
(215, 230, "Event5"),
(215, 415, "Event6"),
(600, 700, "Event7"),
(500, 600, "Event8"),
]
print(get_busy_view(events))
# 输出: [(100, 415), (500, 700)]
复杂度分析
- 时间复杂度：O(n log n)，主要是排序
- 空间复杂度：O(n) 存储结果
进阶：支持多个日历
如果需要合并多个人的日历：
def get_combined_busy_view(calendars: list) -> list:
# 合并所有事件
all_events = []
for calendar in calendars:
all_events.extend(calendar)
return get_busy_view(all_events)
进阶：找出空闲时间段
def get_free_slots(events: list, day_start: int, day_end: int) -> list:
busy = get_busy_view(events)
free = []
current = day_start
for start, end in busy:
if current < start:
free.append((current, start))
current = max(current, end)
if current < day_end:
free.append((current, day_end))
return free
# 找出 0:00 到 24:00 之间的空闲时段
print(get_free_slots(events, 0, 2400))
# 输出: [(0, 100), (415, 500), (700, 2400)]
面试要点
- 边界情况：空列表、只有一个事件、完全不重叠的事件
- 相邻处理：确认 (100, 200) 和 (200, 300) 是否需要合并
- 时间格式：确认时间是分钟数还是 HH:MM 格式
需要面试辅助服务？联系我们
- 📧 Email: [email protected]
- 📱 Phone: +86 17863968105
需要面试真题？ 立刻联系微信 Coding0201，获得真题。