253. Meeting Rooms II

https://leetcode.com/problems/meeting-rooms-ii/leetcode.com

照原本 252, 56 的思路來做的話....只針對 start 排序, 的確是符合這個case

但不符合 ex2, 這樣跑, count 會是 0, 應該預想, 先佔一個 room , 但這樣 ex1 會錯

單單針對 start 排序是不夠的, 以下是錯的

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        // so should sort first
        // e > s  room++ else s = news, e = newe
        // [[0,               30],
        //     [5,10],
        //            [15,20]]
        
        // [2,4] [7,10]
        if (intervals == null || intervals[0].length == 0) return 0;
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        
        int count = 0;
        int start = intervals[0][0];
        int end = intervals[0][1];
        
        for (int i = 1; i < intervals.length; i++) {
            int interval[] = intervals[i];
            if (end > interval[0]) {
                count++;
            } else {
                start = interval[0];
                end = interval[1];
            }
        }
        return count;
    }
}

use line sweep

1.separately sort start, sort end

應該是要改成這樣想

start

| | | |

end

| | | |

start 走到 index 0, 1 時, 都小於 min end

before min end, there are two starts, means 2 rooms are required, count = 2

when start 到 index 2 時, 已經比 min end 大, 代表有一個房間結束了, 所以不需要更多 room,

維持 count = 2, so min end index++

O(logn), O(n)

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        if (intervals == null || intervals.length == 0) return 0;
        int start[] = new int[intervals.length];
        int end[] = new int[intervals.length];
        for (int i = 0; i < intervals.length; i++) {
            start[i] = intervals[i][0];
            end[i] = intervals[i][1];
        }
        Arrays.sort(start);
        Arrays.sort(end);
        
        int endIdx = 0;
        int count = 1;
        for (int i = 1; i < intervals.length; i++) {
            if (start[i] < end[endIdx]) { // no equal, beacuae when [1,13] [13,15], dont need count
                count++;
            } else {
                endIdx++;
            }
        }
        return count;
    }
}

2. use treeMap

這應該是最好寫的 line sweep, 又實用

ex2:
Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2

0+                   30-
     5+. 10-
             15+. 20-
1.   2.  1   2.   1   0      max room count = 2


1 1   -1  1 -1. -1
s s    e. s e.  e
0 5.  10 15 20 30
1 2.  1.  2  1. 0  max room count = 2

time: O(nlogn)

space: O(n)

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        TreeMap<Integer, Integer> map = new TreeMap<>();
        int res = 0;
        for (int[] interval : intervals) {
            int start = interval[0];
            int end = interval[1];
            map.put(start, map.getOrDefault(start, 0) + 1);
            map.put(end, map.getOrDefault(end, 0) - 1);
        }
        
        int count = 0;
        // calculate by key order (tree map), order by time 
        for (int key : map.keySet()) { 
            count += map.get(key);
            res = Math.max(res, count);
        }
        return res;
    }
}

use minHeap

1. sort start time first
2. 
if there is a currStart >= minEnd, means you dont need new room, 
you can reuse the old room,
how to main a minEnd, use minHeap
  
0 1       1
0 1       2
------------- -2, max(current count, max count)
0.  2     3 
  1 2     3   cur count = 2, max count = 3
  1.  4       3    cur count = 3, max count = 3
     3.  6       3  cur count = 3-1+1 = 3, max count = 3 (currStart >= minEnd, 3 >= 2)
     cs 
  
  minEnd = 2, 
  currStart = 1   (1,2), currStart >= minEnd
  
use min heap

01           add, 12 do poll
01. max = 2, add, 14 do poll
0 2.     = 3 add, 36 do poll
 12       3  currStart >= minEnd
 1. 4.    3  currStart >= minEnd
   3. 6.  3  currStart >= minEnd

time : O(nlogn)

space: O(h), heap size, <= n

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        minHeap.offer(intervals[0]);
        
        int count = 1;
        for (int i = 1; i < intervals.length; i++) {
            if (!minHeap.isEmpty() && intervals[i][0] >= minHeap.peek()[1]) {
                minHeap.poll();
            }
            minHeap.offer(intervals[i]);
            count = Math.max(count, minHeap.size());
        }
        return count;
    }
}