最小堆的魅力！思路清晰求解「至少需要多少间会议室」

题目描述

给定一个会议时间安排的数组，每个会议时间都会包括开始和结束的时间 [[ s1 , e1 ] ，[ s2 , e2 ]，…] (si < ei) ，为避免会议冲突，同时要考虑充分利用会议室资源，请你计算至少需要多少间会议室，才能满足这些会议安排。

示例 1:

输入: [[0, 30],[5, 10],[15, 20]]
输出: 2

示例 2:

输入: [[7,10],[2,4]]
输出: 1

题目解析

题目描述是这样的：给定一堆会议的起始和终止时间，问最少需要多少间会议室，比如输入为 [[0, 30],[5, 10],[15, 20]]，输出为 2，输入为 [[7,10],[2,4]]，输出为 1。

拿到一道题先不要急忙着去找最优解，想一想可能的思路有哪些。

随着我们做题数量的增加，往往我们会存在固定思维，习惯用之前的经验快速理解并解决一道题，但是这样其实并不能很好地练习思维发散，我们更应该关注的是一个思路是如何一步步想到的，而不是为了赶紧快速地解决这道题。

一个最直观但是往往不会尝试去想的思路是，取出这里面出现的最大值还有最小值，然后根据这两个值之差建立一个数组，然后计算每个时间点会被多少个会议涵盖，找出最大值即可。

当然上面提到的这种解法在这道题目上时间肯定是不允许的，因为最大值和最小值差距会很大，但是看一道题的时候可以不带着这些限制，这样你可以想出很多有趣的思路和想法。

还是回到这道题，我们现在以区间为基准点来看看怎么解决。一堆会议时间是杂乱无章的，为了让其有序，我们可以将其排序，那么问题是以起始时间排序还是以终止时间排序？

对于这道题，我们需要知道的是，“当一个会议要开始的时候，需不需要另外安排会议室？”，你可以看到，按照这个思路来说，我们考虑的顺序是按照会议开始的时间，因此这里按照会议起始的时间来排序。

排完序之后又遇到一个问题就是，有的会议长有的会议短，当新的一个会议开始的时候，我们要怎么确定这个时候是否有之前空出来的会议室？

因此我们还要对会议的结束时间进行统计，每当一个会议开始，我们就去检查在这个会议之前开始的会议的结束时间的最小值，到这里，你应该能想到堆这个数据结构，没错，我们可以维护一个最小堆用于记录结束时间，这样可以保证整个解的时间复杂度是 O(nlogn) 的。

另外还有一种解法也是比较巧妙，没有用到什么特别的数据结构。这种解法是将所有会议的起始时间和终止时间拆分开来形成两个数组，分别排序，遍历起始时间数组，然后看终止时间数组中是否有结束的会议，记录即可。整个时间复杂度也是 O(nlogn) 的。

参考代码（一）

public int minMeetingRooms(int[][] intervals) {
    if (intervals == null || intervals.length == 0) {
        return 0;
    }

    Arrays.sort(intervals, (int[] a, int[] b) -> (a[0] - b[0]));

    PriorityQueue<Integer> pq = new PriorityQueue<>();

    pq.offer(intervals[0][1]);

    for (int i = 1; i < intervals.length; ++i) {
        if (pq.peek() <= intervals[i][0]) {
            pq.poll();
        }

        pq.offer(intervals[i][1]);
    }

    return pq.size();
}

参考代码（二）

public int minMeetingRooms(int[][] intervals) {
    if (intervals == null || intervals.length == 0) {
        return 0;
    }

    int n = intervals.length;

    int[] start = new int[n];
    int[] end = new int[n];

    for (int i = 0; i < n; ++i) {
        start[i] = intervals[i][0];
        end[i] = intervals[i][1];
    }

    Arrays.sort(start);
    Arrays.sort(end);

    int s = 0, e = 0;
    for (; s < n; s++) {
        if (end[e] <= start[s]) {
            e++;
        }
    }

    return s - e;
}

题目描述

题目解析

参考代码（一）

参考代码（二）

更多相关文章

随机推荐