刷题笔记合集🔗

会议室占用时间

问题描述

现有若干个会议，所有会议共享一个会议室，用数组表示各个会议的开始时间和结束时间，格式为：

[[会议1开始时间, 会议1结束时间], [会议2开始时间, 会议2结束时间]]

请计算会议室占用时间段。

输入格式

第一行输入一个整数 ，表示会议数量。

之后输入 行，每行两个整数，以空格分隔，分别表示会议开始时间，会议结束时间。

输出格式

输出多行，每行两个整数，以空格分隔，分别表示会议室占用时间段开始和结束。

样例输入

4
1 4
2 5
7 9
14 18

2
1 4
4 5

样例输出

1 5
7 9
14 18

1 5

数据范围

• （会议室个数范围）
• 

题解

这道题目本质上是一个区间合并问题。我们需要将重叠或者连续的会议时间合并成一个完整的占用时间段。

解题思路很直观：

1. 首先将所有会议按照开始时间进行升序排序
2. 遍历排序后的会议时间，判断相邻会议是否存在重叠或连续情况
3. 如果存在重叠或连续，则合并这些时间段
4. 如果不存在重叠或连续，则记录前一个时间段，并继续处理后面的会议

具体来说，我们可以取出第一个区间作为基准值pre，从第二个区间cur开始遍历：

• 如果cur的开始时间 <= pre的结束时间，说明两个区间有重叠或连续，应该合并
• 合并的方式是取两个区间的最大结束时间作为新区间的结束时间
• 如果cur的开始时间 > pre的结束时间，说明两个区间无交集，此时将pre记录为一个独立的会议室占用时间，并将cur作为新的基准值

举个例子，假设输入[[1,4],[2,5],[7,9],[14,18]]：

1. 排序后依然是[[1,4],[2,5],[7,9],[14,18]]
2. pre=[1,4]，cur=[2,5]，由于2<=4，两个区间有重叠，合并为[1,5]
3. pre=[1,5]，cur=[7,9]，由于7>5，两个区间无重叠，记录[1,5]，更新pre=[7,9]
4. pre=[7,9]，cur=[14,18]，由于14>9，两个区间无重叠，记录[7,9]，更新pre=[14,18]
5. 最后记录[14,18]

这个算法的时间复杂度是O(nlogn)，主要是排序的时间复杂度。空间复杂度是O(n)，用于存储合并后的结果。

对于给定的数据范围，这个时间复杂度是完全可以接受的。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

# 读取会议数量
n = int(input())

# 读取所有会议时间
meets = []
for _ in range(n):
    s, e = map(int, input().split())
    meets.append([s, e])

# 按会议开始时间排序
meets.sort(key=lambda x: x[0])

# 合并重叠的会议时间
def merge_times(meets):
    # 存储结果数组
    res = []
    # 取第一个区间作为初始值
    cur = meets[0]
    
    # 遍历剩余区间
    for i in range(1, len(meets)):
        # 如果当前区间的开始时间小于等于前一个区间的结束时间，合并区间
        if meets[i][0] <= cur[1]:
            # 更新结束时间为两个区间结束时间的最大值
            cur[1] = max(cur[1], meets[i][1])
        else:
            # 如果没有重叠，将前一个区间加入结