(新卷,100分)- 会议室占用时间（Java JS Python C）

(新卷,100分)- 会议室占用时间（Java & JS & Python & C）

题目描述

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

[[会议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作为新的基准值和后面的区间比较

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

JS算法源码

const rl = require("readline").createInterface({ input: process.stdin }); var iter = rl[Symbol.asyncIterator](); const readline = async () => (await iter.next()).value; // 输入输出处理 void (async function () { const n = parseInt(await readline()); const roomTimes = []; for (let i = 0; i < n; i++) { roomTimes.push((await readline()).split(" ").map(Number)); } merge(roomTimes).forEach(([start, end]) => console.log(`${start} ${end}`)); })(); // 本题实际考试时会核心代码模式，无需处理输入输出，只需要写出merge方法实现即可 function merge(roomTimes) { // 将各个会议按照开始时间升序 roomTimes.sort((a, b) => a[0] - b[0]); // 记录合并后的会议室占用时间段 const ans = []; // 上一个会议占用时间段 let pre = roomTimes[0]; for (let i = 1; i < roomTimes.length; i++) { // 当前会议占用时间段 const cur = roomTimes[i]; if (cur[0] <= pre[1]) { // 当前会议开始时间 <= 上一个会议结束时间，则两个会议时间重叠，可以合并 // 注意合并时，结束时间取两个时间段中较大的结束时间 pre[1] = Math.max(pre[1], cur[1]); } else { // 否则不可以合并 ans.push(pre); pre = cur; } } ans.push(pre); return ans; }

Java算法源码

import java.util.ArrayList; import java.util.Arrays; import java.util.Scanner; public class Main { // 输入输出处理 public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[][] roomTimes = new int[n][2]; for (int i = 0; i < n; i++) { roomTimes[i][0] = sc.nextInt(); roomTimes[i][1] = sc.nextInt(); } int[][] res = new Main().merge(roomTimes); for (int[] time : res) { System.out.println(time[0] + " " + time[1]); } } // 本题实际考试时会核心代码模式，无需处理输入输出，只需要写出merge方法实现即可 public int[][] merge(int[][] roomTimes) { // 将各个会议按照开始时间升序 Arrays.sort(roomTimes, (a, b) -> a[0] - b[0]); // 记录合并后的会议室占用时间段 ArrayList<int[]> list = new ArrayList<>(); // 上一个会议占用时间段 int[] pre = roomTimes[0]; for (int i = 1; i < roomTimes.length; i++) { // 当前会议占用时间段 int[] cur = roomTimes[i]; if (cur[0] <= pre[1]) { // 当前会议开始时间 <= 上一个会议结束时间，则两个会议时间重叠，可以合并 // 注意合并时，结束时间取两个时间段中较大的结束时间 pre[1] = Math.max(pre[1], cur[1]); } else { // 否则不可以合并 list.add(pre); pre = cur; } } list.add(pre); return list.toArray(new int[0][]); } }

Python算法源码

# 本题实际考试时会核心代码模式，无需处理输入输出，只需要写出merge方法实现即可 def merge(roomTimes): # 将各个会议按照开始时间升序 roomTimes.sort(key=lambda x: x[0]) # 记录合并后的会议室占用时间段 ans = [] # 上一个会议占用时间段 pre = roomTimes[0] for i in range(1, len(roomTimes)): # 当前会议占用时间段 cur = roomTimes[i] if cur[0] <= pre[1]: # 当前会议开始时间 <= 上一个会议结束时间，则两个会议时间重叠，可以合并 # 注意合并时，结束时间取两个时间段中较大的结束时间 pre[1] = max(pre[1], cur[1]) else: # 否则不可以合并 ans.append(pre) pre = cur ans.append(pre) return ans # 输入输出处理 n = int(input()) roomTimes = [] for _ in range(n): roomTimes.append(list(map(int, input().split()))) for start, end in merge(roomTimes): print(f"{start} {end}")

C算法源码

#include <stdio.h> #include <stdlib.h> int rows = 0; int cmp(const void *a, const void *b) { return (*(int **) a)[0] - (*(int **) b)[0]; } // 本题实际考试时会核心代码模式，无需处理输入输出，只需要写出merge方法相关实现即可 int **merge(int **roomTimes, int roomTimes_size) { // 将各个会议按照开始时间升序 qsort(roomTimes, roomTimes_size, sizeof(int *), cmp); // 记录合并后的会议室占用时间段 int** res = (int**) malloc(sizeof(int*) * roomTimes_size); // 上一个会议占用时间段 int* pre = roomTimes[0]; // 当前会议占用时间段 for(int i=1; i<roomTimes_size; i++) { int* cur = roomTimes[i]; if(cur[0] <= pre[1]) { // 当前会议开始时间 <= 上一个会议结束时间，则两个会议时间重叠，可以合并 // 注意合并时，结束时间取两个时间段中较大的结束时间 if(cur[1] > pre[1]) { pre[1] = cur[1]; } } else { res[rows++] = pre; pre = cur; } } res[rows++] = pre; return res; } // 输入输出处理 int main() { int n; scanf("%d", &n); int **roomTimes = (int **) malloc(sizeof(int *) * n); for (int i = 0; i < n; i++) { roomTimes[i] = (int *) malloc(sizeof(int) * 2); scanf("%d %d", &roomTimes[i][0], &roomTimes[i][1]); } int **res = merge(roomTimes, n); for (int i = 0; i < rows; i++) { printf("%d %d\n", res[i][0], res[i][1]); } return 0; }