返回目录

题目描述

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

[[会议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]

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

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

Python算法源码

# Python version of the Java code
class Main:
    # 输入输出处理
    def main(self):
        n = int(input())
        room_times = []
        for i in range(n):
            room_times.append(list(map(int, input().split())))

        res = self.merge(room_times)
        for time in res:
            print(time[0], time[1])

    # 实现合并函数
    def merge(self, room_times):
        # 将各个会议按照开始时间升序
        room_times.sort(key=lambda x: x[0])

        # 记录合并后的会议室占用时间段
        merged = []

        # 上一个会议占用时间段
        pre = room_times[0]

        for i in range(1, len(room_times)):
            # 当前会议占用时间段
            cur = room_times[i]

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

        merged.append(pre)

        return merged


# 创建 Main 类的实例并调用 main 方法
if __name__ == "__main__":
    m = Main()
    m.main()

C算法源码

#include <stdio.h>
#include <stdlib.h>

// 定义结构体表示会议室占用时间段
struct Meeting {
    int start;
    int end;
};

// 定义合并函数的原型
struct Meeting* merge(struct Meeting* room_times, int n, int* returnSize);

// 实现合并函数
struct Meeting* merge(struct Meeting* room_times, int n, int* returnSize) {
    // 将各个会议按照开始时间升序
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (room_times[j].start > room_times[j + 1].start) {
                struct Meeting temp = room_times[j];
                room_times[j] = room_times[j + 1];
                room_times[j + 1] = temp;
            }
        }
    }

    // 创建一个数组用于存储合并后的会议室占用时间段
    struct Meeting* merged = (struct Meeting*)malloc(n * sizeof(struct Meeting));
    *returnSize = 0;

    // 上一个会议占用时间段
    struct Meeting pre = room_times[0];

    for (int i = 1; i < n; i++) {
        // 当前会议占用时间段
        struct Meeting cur = room_times[i];

        if (cur.start <= pre.end) {
            // 当前会议开始时间 <= 上一个会议结束时间，则两个会议时间重叠，可以合并
            // 注意合并时，结束时间取两个时间段中较大的结束时间
            pre.end = (pre.end > cur.end) ? pre.end : cur.end;
        } else {
            // 否则不可以合并，将上一个会议室占用时间段添加到合并数组中
            merged[*returnSize] = pre;
            (*returnSize)++;
            pre = cur;
        }
    }

    // 将最后一个会议室占用时间段添加到合并数组中
    merged[*returnSize] = pre;
    (*returnSize)++;

    return merged;
}

// 输入输出处理
int main() {
    int n;
    scanf("%d", &n);

    // 动态分配内存以存储会议室占用时间段
    struct Meeting* room_times = (struct Meeting*)malloc(n * sizeof(struct Meeting));
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &room_times[i].start, &room_times[i].end);
    }

    int returnSize;
    // 调用合并函数
    struct Meeting* res = merge(room_times, n, &returnSize);

    // 输出合并后的会议室占用时间段
    for (int i = 0; i < returnSize; i++) {
        printf("%d %d\n", res[i].start, res[i].end);
    }

    // 释放动态分配的内存
    free(room_times);
    free(res);

    return 0;
}

Java算法源码

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    // 定义内部类表示会议室占用时间段
    static class Meeting {
        int start;
        int end;

        Meeting(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }

    // 实现合并函数
    public static Meeting[] merge(Meeting[] roomTimes) {
        // 将各个会议按照开始时间升序
        Arrays.sort(roomTimes, (a, b) -> a.start - b.start);

        // 创建一个数组用于存储合并后的会议室占用时间段
        Meeting[] merged = new Meeting[roomTimes.length];
        int returnSize = 0;

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

        for (int i = 1; i < roomTimes.length; i++) {
            // 当前会议占用时间段
            Meeting cur = roomTimes[i];

            if (cur.start <= pre.end) {
                // 当前会议开始时间 <= 上一个会议结束时间，则两个会议时间重叠，可以合并
                // 注意合并时，结束时间取两个时间段中较大的结束时间
                pre.end = Math.max(pre.end, cur.end);
            } else {
                // 否则不可以合并，将上一个会议室占用时间段添加到合并数组中
                merged[returnSize++] = pre;
                pre = cur;
            }
        }

        // 将最后一个会议室占用时间段添加到合并数组中
        merged[returnSize++] = pre;

        // 重新调整数组大小，去掉多余的空位
        return Arrays.copyOf(merged, returnSize);
    }

    // 输入输出处理
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        Meeting[] roomTimes = new Meeting[n];

        // 读取会议室占用时间段
        for (int i = 0; i < n; i++) {
            int start = scanner.nextInt();
            int end = scanner.nextInt();
            roomTimes[i] = new Meeting(start, end);
        }

        // 调用合并函数
        Meeting[] res = merge(roomTimes);

        // 输出合并后的会议室占用时间段
        for (Meeting time : res) {
            System.out.println(time.start + " " + time.end);
        }

        scanner.close();
    }
}