(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 %dn", res[i][0], res[i][1]);
    }

    return 0;
}