华为OD机试 - 会议室占用时间段（Java 2024 C卷 100分）

华为OD机试 2024C卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试（JAVA）真题（A卷+B卷+C卷）》。

刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

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

格式为: [[会议1开始时间，会议1结束时间]，[会议2开始时间，会议2结束时间]] 请计算会议室占用时间段。

二、输入描述

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

备注:

会议个数范围: [1,100]

会议室时间段: [1,24]

三、输出描述

输出格式预输入一致,具体请看用例。

[[会议开始时间，会议结束时间]，[会议开始时间，会议结束时间]

1、输入

[[1 ,4],[4,5]]

2、输出

[[1,5]]

四、解题思路

这个问题要求我们找出所有会议的时间段的合并，即计算所有会议时间段的并集。这是一个典型的区间合并问题，可以通过如下步骤解决：

1. 排序: 首先按每个会议的开始时间对会议进行排序。
2. 合并区间: 遍历排序后的会议列表，对于每个会议，如果它与上一个会议有重叠或相接，则合并这两个会议；如果没有重叠，则开始一个新的会议时间段。
3. 输出结果: 所有合并后的会议时间段即为会议室的占用时间段。

五、Java算法源码

public class OdTest01 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        String input = sc.nextLine();
        input = input.substring(1,input.length()-1);
        String[] arr = input.split("],");

        int n = arr.length;

        int[][] meetings = new int[n][2];
        for (int i = 0; i < n; i++) {
            String[] temp = arr[i].replace("[","").replace("]","").split(",");
            meetings[i][0] = Integer.valueOf(temp[0].trim());
            meetings[i][1] = Integer.valueOf(temp[1].trim());
        }

        // 进行会议时间的合并
        List<int[]> mergedMeetings = mergeIntervals(meetings);

        // 构建输出格式
        StringBuilder result = new StringBuilder("[");
        for (int[] meeting : mergedMeetings) {
            if (result.length() > 1) result.append(", ");
            result.append("[").append(meeting[0]).append(", ").append(meeting[1]).append("]");
        }
        result.append("]");

        System.out.println(result);
    }

    private static List<int[]> mergeIntervals(int[][] intervals) {
        // 对区间按照开始时间进行排序
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);

        List<int[]> merged = new ArrayList<>();
        for (int[] interval : intervals) {
            // 如果列表为空或者当前区间与列表中最后区间不重叠，则直接添加
            if (merged.isEmpty() || merged.get(merged.size() - 1)[1] < interval[0]) {
                merged.add(interval);
            } else {
                // 否则，合并当前区间与最后一个区间
                merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], interval[1]);
            }
        }
        return merged;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

六、效果展示

1、输入

[[1,4], [2,5],[7,9], [14,18]]

2、输出

[[1, 5], [7, 9], [14, 18]]

3、说明

时间段[1,4]和[2,5]重叠，合并为[1,5]