华为OD统一考试 - 会议室占用时间

题目描述

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

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

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

输入描述

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

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

输出描述

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

备注

• 会议室个数范围：[1, 100]
• 会议室时间段：[1, 24]

用例

题目解析

本题实际考试时为核心代码模式，非ACM模式，即无需处理输入输出。

本博客代码实现仍然以ACM模式处理，但是会将 "输入输出处理" 与 "核心代码" 分开，大家只看核心代码即可。

本题是区间合并问题。

我们可以将所有区间开始起始位置升序，然后取出第一个区间作为基准值pre，从第二个区间cur开始遍历：

• 如果 cur.start <= pre.end，则说明两个区间有重叠，此时我们应该将两个区间合并，合并策略是将pre.end = max(pre.end, cur.end)，比如：pre = [1, 4]，cur = [2, 5]，那么按此策略合并后，pre = [1, 5]pre = [1, 100]，cur = [7, 9]，那么按此策略合并后，pre = [1, 100]