LeetCode 253 - Meeting Rooms II

LeetCode 252 - Meeting Rooms
http://sbzhouhao.net/LeetCode/LeetCode-Meeting-Rooms-II.html
LIKE CODING: LeetCode [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. Scan line (code)
2. ProrityQueue +
Room Assign + Inroom
Merge (code)
3. 输⼊入时间为字符串串
4. 变种2 当时间不不重 合还要及时pop

1. 简化: Meeting Room
2. 变种: interval变种题, 找出最⼤大利利润情况下，最合适的价格。⽐比如接受
价格范围 A[8, 10] B[6, 8] C[12, 14] 此时定价应该为8因为profit为16(A,B
接受此价格)最⼤大。Interval问题， sort+MinHeap 或者 扫描线
3. 变种：但是给的时间段是string ⽐比如"10a - 10:30a” 难点是 时间的表
达，10AM - 11：30AM 11：00AM to 1PM 怎么存。
4. *是统计每个房间使⽤用过的时间段 譬如[1,5] [3,6] [7,9]就是[[1,5],[7,9]]和
[3,6] 最后问了了对每个房间的时间段做⼀一个merge 譬如[1,5][5,7]就成了了
[1,7]
5. OODesign
https://github.com/mintycc/OnlineJudge-Solutions/blob/master/Leetcode/253_Meeting_Rooms_II.java

X. Using TreeMap: Boundary count
https://leetcode.com/problems/my-calendar-iii/discuss/109556/JavaC%2B%2B-Clean-Code

    public int minMeetingRooms(Interval[] intervals) {
        if (intervals == null || intervals.length == 0) {
            return 0;
        }
        
        TreeMap<Integer, Integer> times = new TreeMap<>();
        for (Interval i : intervals) {
            times.put(i.start, times.getOrDefault(i.start, 0) + 1);
            times.put(i.end, times.getOrDefault(i.end, 0) - 1);
        }
        
        int count = 0, res = 0;
        for (int c : times.values()) {
            count += c;
            res = Math.max(res, count);
        }
        
        return res;
    }

https://leetcode.com/discuss/68125/super-easy-java-solution-using-treemap
public int minMeetingRooms(Interval[] intervals) { Map<Integer, Integer> map = new TreeMap<Integer, Integer>(); // Sort Key based on nature order for (Interval i : intervals) { if (map.containsKey(i.start)) { map.put(i.start, map.get(i.start)+1); } else { map.put(i.start, 1); } if (map.containsKey(i.end)) { map.put(i.end, map.get(i.end)-1); } else { map.put(i.end, -1); } } int maxRoom = 0; int curRoom = 0; for (int i : map.keySet()) { maxRoom = Math.max(maxRoom, curRoom += map.get(i)); } return maxRoom; }

Below is the code with similar algorithm but use TreeMap:

public int minMeetingRooms(Interval[] intervals) {
    //we must sort the timestamp, otherwise we may incorrectly use offset and skip the max room usage
    //key is timeStamp, value is num of room that will be occupied start from this moment. 
    //If a room will be cleared from this moment, then we simply let value--       
    TreeMap<Integer, Integer> hs = new TreeMap<Integer, Integer>();

    for(Interval temp : intervals){
        //put timestamp in map
        if(!hs.containsKey(temp.start)) hs.put(temp.start, 0);
        if(!hs.containsKey(temp.end)) hs.put(temp.end, 0);

        //based on timestamp to mark the usage of rooms
        hs.put(temp.start, hs.get(temp.start) + 1);//add one room
        hs.put(temp.end, hs.get(temp.end) - 1);//remove one room
    }

    int rooms = 0, maxRoom = 0;
    for(int temp : hs.keySet()){
        //update room availability
        rooms += hs.get(temp);
        maxRoom = Math.max(rooms, maxRoom);
    }

    return maxRoom;
}

X.
http://www.jiuzhang.com/solutions/meeting-rooms-ii/

class Point{
    int time;
    int flag;

    Point(int t, int s){
      this.time = t;
      this.flag = s;
    }
    public static Comparator<Point> PointComparator  = new Comparator<Point>(){
      public int compare(Point p1, Point p2){
        if(p1.time == p2.time) return p1.flag - p2.flag;
        else return p1.time - p2.time;
      }
    };
}
    public int minMeetingRooms(Interval[] intervals) {
        List<Point> list = new ArrayList<>(intervals.length*2);
        for(Interval i : intervals){
          list.add(new Point(i.start, 1));
          list.add(new Point(i.end, 0));
        }
    
        Collections.sort(list,Point.PointComparator );
        int count = 0, ans = 0;
        for(Point p : list){
            if(p.flag == 1) {
                count++;
            }
            else {
                count--;
            }
            ans = Math.max(ans, count);
        }
    
        return ans;
    }

X. 
https://leetcode.com/discuss/71846/super-easy-java-solution-beats-98-8%25
Very nice, that lazy releasing of rooms
Rather than create or release a room and keep tracking the max value, you can just add room number when start < end else keep tracking the last class that ends. (Like the idea in this post). 
http://happycoding2010.blogspot.com/2015/11/leetcode-253-meeting-rooms-ii.html

   public int minMeetingRooms(Interval[] intervals) {  
     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].start;  
       end[i]=intervals[i].end;  
     }  
     Arrays.sort(start);  
     Arrays.sort(end);  
     int i=0, j=0, res=0;  
     while (i<n) {  
       if (start[i]<end[j]) i++;  
       else if (start[i]>end[j]) j++;  
       else {  
         i++;  
         j++;  
       }  
       res=Math.max(res,i-j);  
     }  
     return res;  
   }

https://discuss.leetcode.com/topic/31585/elegant-9-line-java-using-heap-6-ms-greedy-java-92-03

Greedy way, much faster than min-heap, while loop is the same as the merge operation of merge-sort.

public int minMeetingRooms(Interval[] intervals) {
    int[] starts = new int[intervals.length], ends = new int[intervals.length];
    for (int i = 0; i < intervals.length; i++) {
        starts[i] = intervals[i].start;
        ends[i] = intervals[i].end;
    }
    Arrays.sort(starts);
    Arrays.sort(ends);
    int i = 0, j = 0, max = 0, cur = 0;
    while (i < starts.length || j < ends.length) {
        if (i >= starts.length) {
            break;
        } else if (starts[i] < ends[j]) {
            cur += 1; i++;
        } else {
            cur -= 1; j++;
        }
        max = Math.max(cur, max);
    }
    return max;
}

https://leetcode.com/discuss/82292/explanation-super-easy-java-solution-beats-from-%40pinkfloyda

To understand why it works, first let’s define two events: Meeting Starts Meeting Ends

Next, we acknowledge three facts: The numbers of the intervals give chronological orders When an ending event occurs, there must be a starting event has happened before that, where “happen before” is defined by the chronological orders given by the intervals Meetings that started which haven’t ended yet have to be put into different meeting rooms, and the number of rooms needed is the number of such meetings

So, what this algorithm works as follows:

for example, we have meetings that span along time as follows:

|_____|
      |______|
|________|
        |_______|

Then, the start time array and end time array after sorting appear like follows:

||    ||
     |   |   |  |

Initially, endsItr points to the first end event, and we move i which is the start event pointer. As we examine the start events, we’ll find the first two start events happen before the end event that endsItr points to, so we need two rooms (we magically created two rooms), as shown by the variable rooms. Then, as i points to the third start event, we’ll find that this event happens after the end event pointed by endsItr, then we increment endsItr so that it points to the next end event. What happens here can be thought of as one of the two previous meetings ended, and we moved the newly started meeting into that vacant room, thus we don’t need to increment rooms at this time and move both of the pointers forward. Next, because endsItr moves to the next end event, we’ll find that the start event pointed by i happens before the end event pointed by endsItr. Thus, now we have 4 meetings started but only one ended, so we need one more room. And it goes on as this.

public int minMeetingRooms(Interval[] intervals) { int[] starts = new int[intervals.length]; int[] ends = new int[intervals.length]; for(int i=0; i<intervals.length; i++) { starts[i] = intervals[i].start; ends[i] = intervals[i].end; } Arrays.sort(starts); Arrays.sort(ends); int rooms = 0; int endsItr = 0; for(int i=0; i<starts.length; i++) { if(starts[i]<ends[endsItr]) rooms++; else endsItr++; } return rooms; }
https://leetcode.com/discuss/74177/elegant-9-line-java-using-heap-%26-6-ms-greedy-java-92-03%25
Greedy way, much faster than min-heap, while loop is the same as the merge operation of merge-sort.

Most greedy solutions start with intuition, and then a few tests that verify that the intuition was correct. I don't have a way to tell right away that a greedy solution will work. I usually start by simply drawing/plotting a sample scenario and observing the behavior. For this problem, I started at putting all the meetings on the same timeline. The idea is that when a new meeting starts, it may require an additional conference room, if one of the running meetings ends we will have a vacant room for the next meeting. So the timeline can look something like this: [s,s,e,s,e,e]: there are three meetings: first meeting starts, then second meeting starts, then first meeting ends, then third meeting starts (it uses the vacant free room from the first meeting that has ended), then second meeting ends, then third meeting ends. The second meeting had no vacant room when it started, so our max # of rooms required increased by 1, the third meeting used one of the vacant rooms that have been added before, so the max # overall is 2. there are 3 things that can happen when meetings overlap (note: I modified my code, the second if-condition didn't make sense and was not necessary): 1. All meetings are already running and no new meetings will start. 2. A new meeting starts before before one of the previous ones ended. 3. A meeting ends. These conditions correspond to the if-statements in the same order. Note, that we don't really care which particular meeting ended or started, we only care that a new meeting has started or any old meeting has ended (look at the timeline array again). In my code, I represent the timeline with two sorted arrays of start times and end times and two pointers. The way we iterate over these two arrays is similar to the merge operation of merge-sort: we advance the pointer with the smaller value (in our case the value represents time). On each iteration of the while loop we simply check whether the current value of rooms required (cur) is the max we've encountered so far. Sorry for the wall of text, I am not very good at explaining :) Let me know if you have any more questions.

public int minMeetingRooms(Interval[] intervals) {
    int[] starts = new int[intervals.length], ends = new int[intervals.length];
    for (int i = 0; i < intervals.length; i++) {
        starts[i] = intervals[i].start;
        ends[i] = intervals[i].end;
    }
    Arrays.sort(starts);
    Arrays.sort(ends);
    int i = 0, j = 0, max = 0, cur = 0;
    while (i < starts.length || j < ends.length) {
        if (i >= starts.length) {
            break;
        } else if (starts[i] < ends[j]) {
            cur += 1; i++;
        } else {
            cur -= 1; j++;
        }
        max = Math.max(cur, max);
    }
    return max;
}

https://leetcode.com/discuss/65801/java-nlog-n-easy-solution-without-heap
public int minMeetingRooms(Interval[] intervals) { int res =0; int temp =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].start; end[i] = intervals[i].end; } Arrays.sort(start); Arrays.sort(end); int i=0; int j=0; while(i<start.length&&j<end.length){ if(start[i]<end[j]){ temp++; i++; res = Math.max(res,temp); } else{ temp--; j++; } } return res; }
http://likesky3.iteye.com/blog/2235665

思路2，参考 
https://leetcode.com/discuss/50793/my-python-solution-with-explanation 
原始注解： 
# Very similar with what we do in real life. Whenever you want to start a meeting, 
# you go and check if any empty room available (available > 0) and 
# if so take one of them ( available -=1 ). Otherwise, 
# you need to find a new room someplace else ( numRooms += 1 ).  
# After you finish the meeting, the room becomes available again ( available += 1 ). 

1.     // Method 2: https://leetcode.com/discuss/50793/my-python-solution-with-explanation  
2.     public int minMeetingRooms(Interval[] intervals) {  
3.         if (intervals == null || intervals.length == 0)  
4.             return 0;  
5.         int N = intervals.length;  
6.         int[] starts = new int[N];  
7.         int[] ends = new int[N];  
8.         for (int i = 0; i < intervals.length; i++) {  
9.             starts[i] = intervals[i].start;  
10.             ends[i] = intervals[i].end;  
11.         }  
12.         Arrays.sort(starts);  
13.         Arrays.sort(ends);  
14.         int e = 0, rooms = 0, available = 0;  
15.         for (int start : starts) {  
16.             while (ends[e] <= start) {  
17.                 available++;  
18.                 e++;  
19.             }  
20.             if (available > 0)  
21.                 available--;  
22.             else  
23.                 rooms++;  
24.         }  
25.         return rooms;  
26.     }  

X. Using Priority Queue
https://discuss.leetcode.com/topic/31585/elegant-9-line-java-using-heap-6-ms-greedy-java-92-03

public int minMeetingRooms(Interval[] intervals) {
    PriorityQueue<int[]> q = new PriorityQueue<>((a,b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
    for (Interval i : intervals) {
        q.offer(new int[] {i.start, 1});
        q.offer(new int[] {i.end, -1});
    }
    int max = 0, cur = 0;
    while(!q.isEmpty())
        max = Math.max(cur += q.poll()[1], max);
    return max;
} 

https://discuss.leetcode.com/topic/20958/ac-java-solution-using-min-heap

public int minMeetingRooms(Interval[] intervals) {
    if (intervals == null || intervals.length == 0)
        return 0;
        
    // Sort the intervals by start time
    Arrays.sort(intervals, new Comparator<Interval>() {
        public int compare(Interval a, Interval b) { return a.start - b.start; }
    });
    
    // Use a min heap to track the minimum end time of merged intervals
    PriorityQueue<Interval> heap = new PriorityQueue<Interval>(intervals.length, new Comparator<Interval>() {
        public int compare(Interval a, Interval b) { return a.end - b.end; }
    });
    
    // start with the first meeting, put it to a meeting room
    heap.offer(intervals[0]);
    
    for (int i = 1; i < intervals.length; i++) {
        // get the meeting room that finishes earliest
        Interval interval = heap.poll();
        
        if (intervals[i].start >= interval.end) {
            // if the current meeting starts right after 
            // there's no need for a new room, merge the interval
            interval.end = intervals[i].end;
        } else {
            // otherwise, this meeting needs a new room
            heap.offer(intervals[i]);
        }
        
        // don't forget to put the meeting room back
        heap.offer(interval);
    }
    
    return heap.size();
}

http://sbzhouhao.net/LeetCode/LeetCode-Meeting-Rooms-II.html

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

        Arrays.sort(intervals, (o1, o2) -> {
            int r = o1.start - o2.start;
            return r == 0 ? o1.end - o2.end : r;
        });

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

        queue.add(intervals[0].end);

        for (int i = 1; i < intervals.length; i++) {
            int val = queue.peek();
            Interval in = intervals[i];
            if (in.start >= val) {
                queue.remove(val);
            }
            queue.add(in.end);
        }
        return queue.size();
    }

使用最小堆来维护所有已安排会议的结束时间，来一个新会议，仍然是比较其start 和 当前最早结束会议时间，若 start >= 最早结束时间，说明该会议可安排，就安排在最早结束那个会议的room，需要从最小堆中删除堆顶元素，将新会议的结束时间插入堆中，否则新增会议室。 
-- seem doesn't work

1.     // Method 1  
2.     public int minMeetingRooms1(Interval[] intervals) {  
3.         if (intervals == null || intervals.length == 0)  
4.             return 0;  
5.         Arrays.sort(intervals, comparator);  
6.         int N = intervals.length;  
7.         int rooms = 1;  
8.         PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();  
9.         minHeap.offer(intervals[0].end);  
10.         for (int i = 1; i < N; i++) {  
11.             if (intervals[i].start < minHeap.peek()) {  
12.                 rooms++;  //works?
13.             } else {  
14.                 minHeap.poll();                  
15.             }  
16.             minHeap.offer(intervals[i].end);  
17.         }  
18.         return rooms;  
19.     } 

X.  http://www.cnblogs.com/jcliBlogger/p/4713099.html
https://leetcode.com/discuss/50783/java-ac-code-using-comparator
Update: for each group of non-overlapping intervals, we just need to store the last added one instead of the full list. So we could use a vector<Interval> instead of vector<vector<Interval>> in C++. The code is now as follows.

 3     int minMeetingRooms(vector<Interval>& intervals) {
 4         sort(intervals.begin(), intervals.end(), compare);
 5         vector<Interval> rooms;
 6         int n = intervals.size();
 7         for (int i = 0; i < n; i++) {
 8             int idx = findNonOverlapping(rooms, intervals[i]);
 9             if (rooms.empty() || idx == -1)
10                 rooms.push_back(intervals[i]);
11             else rooms[idx] = intervals[i];
12         }
13         return (int)rooms.size();
14     } 
15 private:
16     static bool compare(Interval& interval1, Interval& interval2) {
17         return interval1.start < interval2.start;
18     }
19     int findNonOverlapping(vector<Interval>& rooms, Interval& interval) {
20         int n = rooms.size();
21         for (int i = 0; i < n; i++)
22             if (interval.start >= rooms[i].end)
23                 return i;
24         return -1;
25     }

This also group meetings in same meeting room.
The idea is to group those non-overlapping meetings in the same room and then count how many rooms we need. You may refer to this link.

2 public:
 3     int minMeetingRooms(vector<Interval>& intervals) {
 4         sort(intervals.begin(), intervals.end(), compare);
 5         vector<vector<Interval>> rooms;
 6         int n = intervals.size();
 7         for (int i = 0; i < n; i++) {
 8             int idx = findNonOverlapping(rooms, intervals[i]);
 9             if (rooms.empty() || idx == -1)
10                 rooms.push_back({intervals[i]});
11             else rooms[idx].push_back(intervals[i]);
12         }
13         return (int)rooms.size();
14     }
15 private:
16     static bool compare(Interval& interval1, Interval& interval2) {
17         return interval1.start < interval2.start;
18     }
19     int findNonOverlapping(vector<vector<Interval>>& rooms, Interval& interval) {
20         int n = rooms.size();
21         for (int i = 0; i < n; i++)
22             if (interval.start >= rooms[i].back().end)
23                 return i;
24         return -1;
25     }

X.  Use PriorityQueue + sweep line
https://discuss.leetcode.com/topic/20958/ac-java-solution-using-min-heap/11

public int minMeetingRooms(Interval[] intervals) {
    if (intervals == null || intervals.length == 0)
        return 0;
        
    // Sort the intervals by start time
    Arrays.sort(intervals, new Comparator<Interval>() {
        public int compare(Interval a, Interval b) { return a.start - b.start; }
    });
    
    // Use a min heap to track the minimum end time of merged intervals
    PriorityQueue<Interval> heap = new PriorityQueue<Interval>(intervals.length, new Comparator<Interval>() {
        public int compare(Interval a, Interval b) { return a.end - b.end; }
    });
    
    // start with the first meeting, put it to a meeting room
    heap.offer(intervals[0]);
    
    for (int i = 1; i < intervals.length; i++) {
        // get the meeting room that finishes earliest
        Interval interval = heap.poll();
        
        if (intervals[i].start >= interval.end) {
            // if the current meeting starts right after 
            // there's no need for a new room, merge the interval
            interval.end = intervals[i].end;
        } else {
            // otherwise, this meeting needs a new room
            heap.offer(intervals[i]);
        }
        
        // don't forget to put the meeting room back
        heap.offer(interval);
    }
    
    return heap.size();
}

public int minMeetingRooms(Interval[] intervals) {
 if (intervals.length == 0) {
  return 0;
 }
 // sort
 Arrays.sort(intervals, new Comparator<Interval>() {
  @Override
  public int compare(Interval a, Interval b) {
   return a.start - b.start;
  }
 });
 // PriorityQueue
 PriorityQueue<Integer> ends = new PriorityQueue<Integer>();
 ends.offer(intervals[0].end);
 for (int i = 1; i < intervals.length; i++) {
  if (intervals[i].start >= ends.peek()) { // no overlap, then should update smallest end.
   ends.poll();
  } 
  ends.offer(intervals[i].end);
 }
 return ends.size();
}

A different version of code with similar thought. Every time the new interval start is larger than the minimum end, pop the interval in the queue.

    public int minMeetingRooms(Interval[] intervals) {
        if(intervals == null || intervals.length == 0) return 0;
        Arrays.sort(intervals, (a, b) -> (a.start - b.start));
        int max = 0;
        PriorityQueue<Interval> queue = new PriorityQueue<>(intervals.length, (a, b) -> (a.end - b.end));
        for(int i = 0; i < intervals.length; i++){
            while(!queue.isEmpty() && intervals[i].start >= queue.peek().end)
                queue.poll();
            queue.offer(intervals[i]);
            max = Math.max(max, queue.size());
        }
        return max;
    }

http://www.cnblogs.com/yrbbest/p/5012534.html

给定一个interval数组，求最少需要多少间教室。初始想法是扫描线算法sweeping-line algorithm，先把数组排序，之后维护一个min-oriented heap。遍历排序后的数组，每次把interval[i].end加入到heap中，然后比较interval.start与pq.peek()，假如interval[i].start >= pq.peek()，说明pq.peek()所代表的这个meeting已经结束，我们可以从heap中把这个meeting的end time移除，继续比较下一个pq.peek()。比较完毕之后我们尝试更新maxOverlappingMeetings。 像扫描线算法和heap还需要好好复习， 直线，矩阵的相交也可以用扫描线算法。

Time Complexity - O(nlogn)， Space Complexity - O(n)

    public int minMeetingRooms(Interval[] intervals) {
        if(intervals == null || intervals.length == 0)
            return 0;
        
        Arrays.sort(intervals, new Comparator<Interval>() {
            public int compare(Interval t1, Interval t2) {
                if(t1.start != t2.start)
                    return t1.start - t2.start;
                else
                    return t1.end - t2.end;
            }
        });
        
        int maxOverlappingMeetings = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>();      // min oriented priority queue
        
        for(int i = 0; i < intervals.length; i++) {         // sweeping-line algorithms
            pq.add(intervals[i].end);
            while(pq.size() > 0 && intervals[i].start >= pq.peek())
                pq.remove();
                
            maxOverlappingMeetings = Math.max(maxOverlappingMeetings, pq.size());
        }
        
        return maxOverlappingMeetings;
    }

Use min PQ to store the meeting rooms end time. If new meeting start time greater or equal than least element, update it. If not open a new meeting room. Report the pq size at the end. O(nlogn) complexity.
http://segmentfault.com/a/1190000003894670
An alternative solution is to use a priority queue to store the end times. Then we sort the intervals according to its start time. We iterate through the intervals. If the current start time is less than the earliest end time in the pq, numRooms++. Else, remove the earliest time from the pq. For each iteration, we also need to offer the current ending time into the pq. 

这题的思路和Rearrange array to certain distance很像，我们要用贪心法，即从第一个时间段开始，选择下一个最近不冲突的时间段，再选择下一个最近不冲突的时间段，直到没有更多。然后如果有剩余时间段，开始为第二个房间安排，选择最早的时间段，再选择下一个最近不冲突的时间段，直到没有更多，如果还有剩余时间段，则开辟第三个房间，以此类推。这里的技巧是我们不一定要遍历这么多遍，我们实际上可以一次遍历的时候就记录下，比如第一个时间段我们放入房间1，然后第二个时间段，如果和房间1的结束时间不冲突，就放入房间1，否则开辟一个房间2。然后第三个时间段，如果和房间1或者房间2的结束时间不冲突，就放入房间1或者2，否则开辟一个房间3，依次类推，最后统计开辟了多少房间。对于每个房间，我们只要记录其结束时间就行了，这里我们查找不冲突房间时，只要找结束时间最早的那个房间。
这里还有一个技巧，如果我们把这些房间当作List来管理，每次查询需要O(N)时间，如果我们用堆来管理，可以用logN时间找到时间最早结束的房间。

    public int minMeetingRooms(Interval[] intervals) {
        if(intervals == null || intervals.length == 0) return 0;
        Arrays.sort(intervals, new Comparator<Interval>(){
            public int compare(Interval i1, Interval i2){
                return i1.start - i2.start;
            }
        });
        // 用堆来管理房间的结束时间
        PriorityQueue<Integer> endTimes = new PriorityQueue<Integer>();
        endTimes.offer(intervals[0].end);
        for(int i = 1; i < intervals.length; i++){
            // 如果当前时间段的开始时间大于最早结束的时间，则可以更新这个最早的结束时间为当前时间段的结束时间，如果小于的话，就加入一个新的结束时间，表示新的房间
            if(intervals[i].start >= endTimes.peek()){
                endTimes.poll();
            }
            endTimes.offer(intervals[i].end);
        }
        // 有多少结束时间就有多少房间
        return endTimes.size();
    }

https://leetcode.com/discuss/51402/java-greedy-algorithm-with-priority-queue
public int minMeetingRooms(Interval[] intervals) { if (intervals == null || intervals.length == 0) return 0; Comparator<Interval> comp = new Comparator<Interval>() { @Override public int compare(Interval o1, Interval o2) { return o1.start - o2.start; } }; Arrays.sort(intervals, comp); PriorityQueue<Interval> queue = new PriorityQueue<Interval>(intervals.length, new Comparator<Interval>() { @Override public int compare(Interval o1, Interval o2) { return o1.end - o2.end; } } ); for (int i = 0; i < intervals.length; i++) { if (queue.isEmpty()) { queue.offer(intervals[i]); //start the first meeting in a new room. } else { Interval finishingMeeting = queue.poll(); // get the previous meeting with earliest finishing time. if (intervals[i].start < finishingMeeting.end) { queue.offer(intervals[i]); //the meeting isn't finished yet, start meeting in a new room. } else { finishingMeeting.end = intervals[i].end; // using the room by the previous meeting. } queue.offer(finishingMeeting); } } return queue.size(); }
https://leetcode.com/discuss/50911/ac-java-solution-using-min-heap

A different version of code with similar thought. Every time the new interval start is larger than the minimum end, pop the interval in the queue. In addition, really enjoy the java 8 lambda style comparator : )

public int minMeetingRooms(Interval[] intervals) { if(intervals == null || intervals.length == 0) return 0; Arrays.sort(intervals, (a, b) -> (a.start - b.start)); int max = 0; PriorityQueue<Interval> queue = new PriorityQueue<>(intervals.length, (a, b) -> (a.end - b.end)); for(int i = 0; i < intervals.length; i++){ while(!queue.isEmpty() && intervals[i].start >= queue.peek().end) queue.poll(); queue.offer(intervals[i]); max = Math.max(max, queue.size()); } return max; }
http://dananqi.blog.163.com/blog/static/23066615020157104293164/

这题就是首先按照start time 排序，然后遍历排序后的数组.

如果当前会议的开始时间早于之前所有会议的结束时间(即最早结束的会议），则要增加一个房间。

如果之前所有会议的最早结束时间早于当前会议，那么不需要增加会议室，只需要重新记下最早结束的会议就好了。

所以关键在要记住当前所有会议的最早结束时间，需要借助一个min heap，比较的是结束时间。

而之前排序的时候要比较的是开始时间。这个算法的时间复杂度为O(NlogN)。

如果不用heap，也可以用一个List<Interval> 来记录下每个会议室的结束时间，每次遇到一个新的会议，则要寻找是否有会议室已经结束了，如果找到，不用增加会议室，如果没找到，则要增加。这种解法每次都要遍历一遍所有会议室，最坏情况下为O(N*N)。不如上面用heap的时间复杂度为O(NlogN)。

public int minMeetingRooms(Interval[] intervals) {
if(intervals == null || intervals.length == 0) return 0;
int len = intervals.length;
Arrays.sort(intervals, new Comparator<Interval>() {
public int compare(Interval i, Interval j) { return i.start - j.start; }
});
PriorityQueue<Interval> heap = new PriorityQueue<Interval>(len, new Comparator<Interval>() {
public int compare(Interval i, Interval j) { return i.end - j.end; }
});
heap.offer(intervals[0]);
for(int i = 1; i < len; i++) {
Interval min = heap.poll();
if(intervals[i].start >= min.end) {
min.end = intervals[i].end; //更新当前最早结束
} else {
heap.offer(intervals[i]); //增加一个会议室
}
heap.offer(min); //当前最早结束有可能已经更新了哦。
}
return heap.size();
}

X. PriorityQueue + Event
https://discuss.leetcode.com/topic/25503/java-another-thinking-process-event-queue/2

Simulate event queue procession. Create event for each start and end of intervals. Then for start event, open one more room; for end event, close one meeting room. At the same time, update the most rooms that is required.

Be careful of events like [(end at 11), (start at 11)]. Put end before start event when they share the same happening time, so that two events can share one meeting room.

    private static final int START = 1;

    private static final int END = 0;
    
    private class Event {
        int time;
        int type; // end event is 0; start event is 1

        public Event(int time, int type) {
            this.time = time;
            this.type = type;
        }
    }
    
    public int minMeetingRooms(Interval[] intervals) {
        int rooms = 0; // occupied meeting rooms
        int res = 0;

        // initialize an event queue based on event's happening time
        Queue<Event> events = new PriorityQueue<>(new Comparator<Event>() {
            @Override
            public int compare(Event e1, Event e2) {
                // for same time, let END event happens first to save rooms
                return e1.time != e2.time ? 
                       e1.time - e2.time : e1.type - e2.type;
            }
        });

        // create event and push into event queue
        for (Interval interval : intervals) {
            events.offer(new Event(interval.start, START));
            events.offer(new Event(interval.end, END));
        }
        
        // process events
        while (!events.isEmpty()) {
            Event event = events.poll();
            if (event.type == START) {
                rooms++;
                res = Math.max(res, rooms);
            } else {
                rooms--; 
            }
        }
        
        return res;
    }

X.
https://leetcode.com/discuss/50783/java-ac-code-using-comparator

Nice idea to just group those non-overlapping meetings together :-)

A little improvement: for each group of non-overlapping intervals, we just need to store the last added one instead of the full list. So we could use a vector<Interval> instead ofvector<vector<Interval>> in C++ or a List<Interval> instead of List<List<Interval>>in Java.

class intervalComparator implements Comparator<Interval>{
    public int compare(Interval o1, Interval o2){
        return o1.start-o2.start;
    }
}
public int minMeetingRooms(Interval[] intervals) {
    Arrays.sort(intervals, new intervalComparator());
    List<List<Interval>> list = new ArrayList<>();
    for(int i=0; i<intervals.length; i++){
        int idx = findIdx(list, intervals[i]);
        if(list.size()==0 || idx==-1){
            List<Interval> tmp = new ArrayList<>();
            tmp.add(intervals[i]);
            list.add(tmp);
        }else{
            list.get(idx).add(intervals[i]);
        }
    }
    return list.size();
}
public int findIdx(List<List<Interval>> list, Interval interval){
    int idx = -1;
    int min=Integer.MAX_VALUE;
    for(int i=0; i<list.size(); i++){
        if(interval.start>=list.get(i).get(list.get(i).size()-1).end){
            return i;
        }
    }
    return idx;
}

 it depends on number of rooms. The worst case is O(NlogN + NN) --> O(N^2). Normal case is O(NlogN + Nk), while k is the room number
int minMeetingRooms(vector<Interval>& intervals) { sort(intervals.begin(), intervals.end(), compare); vector<Interval> rooms; int n = intervals.size(); for (int i = 0; i < n; i++) { int idx = findNonOverlapping(rooms, intervals[i]); if (rooms.empty() || idx == -1) rooms.push_back(intervals[i]); else rooms[idx] = intervals[i]; } return (int)rooms.size(); } private: static bool compare(Interval& interval1, Interval& interval2) { return interval1.start < interval2.start; } int findNonOverlapping(vector<Interval>& rooms, Interval& interval) { int n = rooms.size(); for (int i = 0; i < n; i++) if (interval.start >= rooms[i].end) return i; return -1; }

X. https://leetcode.com/discuss/60659/java-another-thinking-process-event-queue

Simulate event queue procession. Create event for each start and end of intervals. Then forstart event, open one more room; for end event, close one meeting room. At the same time, update the most rooms that is required.

Be careful of events like [(end at 11), (start at 11)]. Put end before start event when they share the same happening time, so that two events can share one meeting room.

public class Solution { private static final int START = 1; private static final int END = 0; private class Event { int time; int type; // end event is 0; start event is 1 public Event(int time, int type) { this.time = time; this.type = type; } } public int minMeetingRooms(Interval[] intervals) { int rooms = 0; // occupied meeting rooms int res = 0; // initialize an event queue based on event's happening time Queue<Event> events = new PriorityQueue<>(new Comparator<Event>() { @Override public int compare(Event e1, Event e2) { // for same time, let END event happens first to save rooms return e1.time != e2.time ? e1.time - e2.time : e1.type - e2.type; } }); // create event and push into event queue for (Interval interval : intervals) { events.offer(new Event(interval.start, START)); events.offer(new Event(interval.end, END)); } // process events while (!events.isEmpty()) { Event event = events.poll(); if (event.type == START) { rooms++; res = Math.max(res, rooms); } else { rooms--; } } return res; } }

https://leetcode.com/discuss/62683/simple-o-nlgn-java-solution-with-explanation

The basic idea is referred from StefanPochmann's C++ version: Create a map to store room amount changes for each meeting time point, if it's start time, room + 1; if it's end time, room - 1. Then sort the keys of the map, iterate the room changes, eventually output the maximum room amount as the result.

public int minMeetingRooms(Interval[] intervals) { HashMap<Integer, Integer> changes= new HashMap<Integer, Integer>();//Room changes at the specific time. for (Interval i : intervals) { Integer start = changes.get(i.start) == null ? 0 : changes.get(i.start); changes.put(i.start, start+1); Integer end = changes.get(i.end) == null ? 0 : changes.get(i.end); changes.put(i.end, end-1); } int rooms = 0, maxrooms = 0; Object array[] = changes.keySet().toArray(); Arrays.sort(array); for (Object i : array) { rooms += changes.get(i); maxrooms = Math.max(maxrooms, rooms); } return maxrooms; }

Below code can be avoid if you use TreeMap in java, where key is sorted

    Object array[] = changes.keySet().toArray();
    Arrays.sort(array);

public int minMeetingRooms(Interval[] intervals) { PriorityQueue<int[]> q = new PriorityQueue<>((a,b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]); for (Interval i : intervals) { q.offer(new int[] {i.start, 1}); q.offer(new int[] {i.end, -1}); } int max = 0, cur = 0; while(!q.isEmpty()) max = Math.max(cur += q.poll()[1], max); return max; }
http://buttercola.blogspot.com/2015/08/leetcode-meeting-rooms-ii.html

    public int minMeetingRooms(Interval[] intervals) {

        if (intervals == null || intervals.length == 0) {

            return 0;

        }

         

        int len = intervals.length;

        int[] startTime = new int[len];

        int[] endTime = new int[len];

         

        for (int i = 0; i < len; i++) {

            Interval curr = intervals[i];

            startTime[i] = curr.start;

            endTime[i] = curr.end;

        }

         

        // Sort the start and end time

        Arrays.sort(startTime);

        Arrays.sort(endTime);

         

        int activeMeetings = 0;

        int numMeetingRooms = 0;

         

        int i = 0;

        int j = 0;

         

        while (i < len && j < len) {

            if (startTime[i] < endTime[j]) {

                activeMeetings++;

                numMeetingRooms = Math.max(numMeetingRooms, activeMeetings);

                i++;

            } else {

                activeMeetings--;

                j++;

            }

        }

         

        return numMeetingRooms;

    }

https://leetcode.com/discuss/70998/java-ac-solution-greedy-beats-92-03%25

According to greedy, you get one interval, then add the one right behind it. Then recursively deal with the rest.

    public int minMeetingRooms(Interval[] intervals) {
        Arrays.sort(intervals, new Comparator<Interval>(){
           public int compare(Interval o1, Interval o2){
               return o1.start - o2.start;
           } 
        });
        return helper(new ArrayList(Arrays.asList(intervals)));
    }

    private int helper(List<Interval> li){
        if(li.size() == 0)
            return 0;
        Interval pre = li.get(0);
        List<Interval> nextLi = new ArrayList();
        for(int i=1;i<li.size();i++){
            Interval inter = li.get(i);
            if(inter.start < pre.end){
                nextLi.add(inter);
            }else{
                pre = inter;
            }
        }
        return 1 + helper(nextLi);
    }

http://www.jyuan92.com/blog/leetcode-meeting-rooms-ii/

Follow up
http://www.1point3acres.com/bbs/thread-210807-1-1.html

• 一大堆Task有开始时间和结束时间，要把这些工作派给不同的工人
• 每个工人有一个list存放自己要做的Task
• 要求把这些工作尽可能的安排给少的工人，存在他们的工作List里面
• 最后返回这些工人

我一上来就是Meeting Room 2 的思路
在meeting room2 里， 最常规的思路就是分开看，开始时间和结束时间，然后做完了就可以做新的，有会还在开的时候就得加一个会议室，这里跟这个很相似，我每次都找到所有现有worker中工作最早做完的那一个，然后跟最近开始的工作的开始时间作比较，如果来的记做就安排给他，来不及就加个新的。 当时时间紧也没有细想对不对。。。

airbnb面试题汇总

给一组meetings（每个meeting由start和end时间组成）。求出在所有输入meeting时间段内没有会议，也就是空闲的时间段。每个subarray都已经sort好。N个员工，每个员工有若干个interval表示在这段时间是忙碌的。求所有员工都不忙的intervals。

循环merge，然后遍历空闲区间（ps：另一种解法很简单，参考：这题最简单的方法就是把所有区间都拆成两个点，然后排序，然后扫描，每次碰到一个点如果是左端点就把busy_employees加1，否则减1，等到每次busy_employees为0时就是一个新的区间。这样复杂度O(MlogM)，M是总共区间数。）

//merge and search
vector<pr> merge(vector<pr> ft, vector<pr> sd) {//c++, merge
    if(ft.empty()) return sd;
    if(sd.empty()) return ft;
    vector<pr> ans;
    const int m = ft.size(), n = sd.size();
    int i = 0, j = 0;
    pr tmp(1, 1);
    while(i < m || j < n) {
        if ((i == m || tmp.second < ft[i].first) && (j == n || tmp.second < sd[j].first)) {
            ans.push_back(tmp);
            if(i == m) tmp = sd[j];
            else if(j == n) tmp = ft[i];
            else {
                tmp.first = min(ft[i].first, sd[j].first);
                tmp.second = min(ft[i].second, sd[j].second);
            }
        }
        if(i < m && ft[i].first <= tmp.second)
            tmp.second = max(tmp.second, ft[i++].second);
        if(j < n && sd[j].first <= tmp.second)
            tmp.second = max(tmp.second, sd[j++].second);
    }
    ans.push_back(tmp);
    return ans;
}
vector<pr> meetingRoom(vector<vector<pr> > meetings) {
    vector<pr> ans, tmp;
    const int n = meetings.size();
    if(n == 0) return ans;
    tmp = meetings[0];
    for(int i = 1; i < n; ++i) {
        tmp = merge(tmp, meetings[i]);
    }
    if(tmp[0].first > 1)
        ans.push_back(make_pair(1, tmp[0].first));
    for(int i = 0; i < tmp.size() - 1; ++i)
        ans.push_back(make_pair(tmp[i].second, tmp[i + 1].first));
    return ans;
}

//break and sort: C++
typedef pair<int, int> pr;
typedef pair<int, bool> timePoint;
vector<pr> meetingRoom(vector<vector<pr> > meetings) {
    vector<timePoint> times;
    vector<pr> ans;
    if ( meetings.empty()) return ans;
    for (auto meeting : meetings) {
        for (auto interval : meeting) {
            times.push_back(make_pair(interval.first, true));
            times.push_back(make_pair(interval.second, false));
        }
    }
    sort(times.begin(), times.end());
    int startCnt = 0, preTime = times[0].first;
    for(auto time : times) {
        bool starting = time.second;
        if (starting) {
            if (startCnt == 0 && time.first > preTime) {
                ans.push_back(make_pair(preTime, time.first));
            }
            ++startCnt;
        } else {
            if (startCnt == 1) preTime = max(preTime, time.first);
            --startCnt;
        }
    }
    return ans;
}

//break and sort: python    
def find_free_time(schedules):
moment_status = []

for person_schedule in schedules:
    for interval in person_schedule:
        moment_status.append((interval[0], True))
        moment_status.append((interval[1], False))
moment_status.sort()
free_start = moment_status[0][0]
busy_count = 0
available_intervals = []
for moment, become_busy in moment_status:
    if become_busy:
        if busy_count == 0:
            if moment > free_start:
                available_intervals.append((free_start, moment))
        busy_count += 1
    else:
        if busy_count == 1:
            free_start = moment
        busy_count -= 1
return available_intervals

Read full article from LIKE CODING: LeetCode [253] Meeting Rooms II