253. Meeting Rooms II

发表于 | 分类于

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],…] (si < ei), find the minimum number of conference rooms required.

For example,
Given [[0, 30],[5, 10],[15, 20]],
return 2

解法1： Sweep Line / 扫描线

扫描线的基础题。基本的思路是把所有的线段的两个断点都归类并且排序，然后碰到起点就+1，碰到终点就-1，按照时间的顺序遍历，相当于有一根线在从左面扫到右面。
实际在写code的时候可以有不同的写法，第一种是用了一种比较少用的数据结构，TreeMap。这个hashmap存储的是对于每一个时间点的计数，不同的是，对于起点计数+1，对于终点计数-1， 表现的就是如果一个会议结束了当前的room就释放出来不需要了，所以自然需要的room的个数-1。然后需要按照时间顺序遍历每一个时间点，把所有的room的变化加和，在加和的过程中保留下遇见过的最大值）。TreeMap的key是按照natural order排序的，所以很适合这个问题。

lang: java
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
/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
class Solution {
    public int minMeetingRooms(Interval[] intervals) {
        if (intervals == null || intervals.length == 0) {
            return 0;
        }
        //
        Map<Integer, Integer> map = new TreeMap<>();    // Treat start and end as the natural time point
        // Takes O(logN) for each operation
        for (Interval it : intervals) {
            map.put(it.start, map.getOrDefault(it.start, 0) + 1);
            map.put(it.end, map.getOrDefault(it.end, 0) - 1);
        }
        int rooms = 0;
        int res = 0;
        for (int timePoint : map.keySet()) {
            // timePoint is sorted in ascending order
            rooms += map.get(timePoint);
            res = Math.max(res, rooms);
        }
        return res;
    }
}

解法2： Sorting Array

同样的思路，不同的写法。也可以维护两个数组，start, end. 把对应的时间点放进去进行排序。然后用两个指针指向两个数组，当start < end的时候需要的room+1， 反之则room-1. 然后在更新的过程中统计出现过的最大的room的个数。

lang: java
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
/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
class Solution {
    public int minMeetingRooms(Interval[] intervals) {
        int n = intervals.length;
        int[] start = new int[n];
        int[] end = new int[n];
        for (int i = 0; i < intervals.length; i++) {
            start[i] = intervals[i].start;
            end[i] = intervals[i].end;
        }
        Arrays.sort(start);
        Arrays.sort(end);
        int endptr = 0;
        int res = 0;
        for (int i = 0; i < n; i++) {
            if (start[i] < end[endptr]) {
                res++;
            } else {
                endptr++;
            }
        }
        return res;
    }
}