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

OD统一考试

题解： Java / Python / C++

题目描述

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

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

输入描述

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

备注:

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

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

输出描述

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

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

示例1

输入:
[[1,4], [2,5],[7,9], [14,18]]

输出:
[[1,5], [7,9],[14,18]]

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

示例2

输入:
[[1 ,4],[4,5]]

输出:
[[1,5]]

说明

此题为核心编码模式，非ACM模式。

题解

排序 + 模拟

如果我们按照区间的左端点排序，那么在排完序的列表中，可以合并的区间一定是连续的。

算法描述

我们用数组 merged 存储最终的答案。

首先，我们将列表中的区间按照左端点升序排序。然后我们将第一个区间加入 merged 数组中，并按顺序依次考虑之后的每个区间：

如果当前区间的左端点在数组 merged 中最后一个区间的右端点之后，那么它们不会重合，我们可以直接将这个区间加入数组 merged 的末尾；

否则，它们重合，我们需要用当前区间的右端点更新数组 merged 中最后一个区间的右端点，将其置为二者的较大值。

Java

/**
 * @author code5bug
 */
class Solution {
    public int[][] merge(int[][] roomTimes) {
        if (roomTimes.length == 0) {
            return new int[0][2];
        }
        Arrays.sort(roomTimes, new Comparator<int[]>() {
            public int compare(int[] time1, int[] time2) {
                return time1[0] - time2[0];
            }
        });
        List<int[]> merged = new ArrayList<int[]>();
        for (int i = 0; i < roomTimes.length; ++i) {
            int L = roomTimes[i][0], R = roomTimes[i][1];
            if (merged.size() == 0 || merged.get(merged.size() - 1)[1] < L) {
                merged.add(new int[]{L, R});
            } else {
                merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], R);
            }
        }
        return merged.toArray(new int[merged.size()][]);
    }
}

Python

class Solution:
    def merge(self, roomTimes: List[List[int]]) -> List[List[int]]:
        intervals.sort()
        merged = []
        for time in roomTimes:
            # 如果列表为空，或者当前区间与上一区间不重合，直接添加
            if not rs or rs[-1][1] < time[0]:
                merged.append(time)
            else:
                # 否则的话，我们就可以与上一区间进行合并
				merged[-1][1] = max(merged[-1][1], time[1])

        return merged

C++

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& roomTimes) {
        if (intervals.size() == 0) {
            return {};
        }
        sort(roomTimes.begin(), roomTimes.end());
        vector<vector<int>> merged;
        for (int i = 0; i < roomTimes.size(); ++i) {
            int L = roomTimes[i][0], R = roomTimes[i][1];
            if (!merged.size() || merged.back()[1] < L) {
                merged.push_back({L, R});
            }else {
                merged.back()[1] = max(merged.back()[1], R);
            }
        }
        return merged;
    }
};

相关练习题

整理题解不易， 如果有帮助到您，请给点个赞 ‍❤️‍ 和收藏 ⭐，让更多的人看到。