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

题目描述

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

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

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

输入描述

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

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

输出描述

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

备注

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

用例

题目解析

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

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

import Foundation

func ODTest_2_48() {
    print("输入描述")
    print("第一行输入一个整数 n，表示会议数量")
    let n = Int(readLine() ?? "") ?? 0
    print("之后输入n行，每行两个整数，以空格分隔，分别表示会议开始时间，会议结束时间")
    var roomTimes: [[Int]] = Array(repeating: Array(repeating: 0, count: 2), count: n)
    for i in 0 ..< n {
        let data = (readLine() ?? "").split(separator: " ").map { Int($0) ?? 0 }
        roomTimes[i][0] = data[0]
        roomTimes[i][1] = data[1]
    }

    let res = merge()
    
    print("输出多行，每个两个整数，以空格分隔，分别表示会议室占用时间段开始和结束")
    print("\(res.map { "\($0[0]) \($0[1])" }.joined(separator: "\r\n"))")
    // 本题实际考试时会核心代码模式，无需处理输入输出，只需要写出merge方法实现即可
    func merge() -> [[Int]] {
        // 将各个会议按照开始时间升序
        roomTimes.sort(by: { $0[0] < $1[1] })

        // 记录合并后的会议室占用时间段
        var list: [[Int]] = []

        // 上一个会议占用时间段
        var pre = roomTimes[0]

        for i in 1 ..< roomTimes.count {
            // 当前会议占用时间段
            let cur = roomTimes[i]

            if cur[0] <= pre[1] {
                // 当前会议开始时间 <= 上一个会议结束时间，则两个会议时间重叠，可以合并
                // 注意合并时，结束时间取两个时间段中较大的结束时间
                pre[1] = max(pre[1], cur[1])
            } else {
                // 否则不可以合并
                list.append(pre)
                pre = cur
            }
        }

        list.append(pre)

        return list
    }
}

本题是区间合并问题。

我们可以将所有区间开始起始位置升序，然后取出第一个区间作为基准值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]
• 如果 cur.start > pre.end，则说明两个区间无交集，此时pre无法和后面任何区间合并（因为已经按照开始时间升序了，后面区间的开始时间肯定也大于pre.end），此时pre时间段就是一个独立的会议室占用时间，我们将它缓存记录下来，并将更新pre = cur，即将cur作为新的基准值和后面的区间比较

按此逻辑，即可完成所有区间的合并。