欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Leetcode 253 Meeting Rooms II

程序员文章站 2022-03-11 21:56:59
...

Leetcode 253 Meeting Rooms II
思路一: 追踪目前已经使用的房间个数。先以开始时间sort数组,然后遍历数组,check前面遍历过的会议有没有已经结束的。有的话当前的会议就可以去结束的那个会议所在的房间,房间数就不用+1;如果前面的会议都没有结束,则需要新开一间房间,那么房间数+1。整个过程中持续追踪房间数的最大值,这个最大值即是答案。我的这个思路其实和approach 1一样的,只是他用了min heap(最小优先队列)。其实这整个开会的事件不就像最小优先队列吗。队列队列,顾名思义,要排队的嘛。开会的话,也是按开始时间一个个排队的嘛。我这么比较l也许不是特别准确,但是先后顺序的问题确实要考虑优先队列这个数据结构。下面展示我的代码以及approach1代码:

// 我的代码
class Solution {
    public int minMeetingRooms(int[][] intervals) {
        int room = 0;
        int res = 0;
        List<int[]> processing = new ArrayList<>();
        Arrays.sort(intervals, (o1, o2) -> o1[0] - o2[0]);
        for(int i = 0; i < intervals.length; i++){
            if(processing.isEmpty()){
                processing.add(intervals[i]);
                room++;
                res = Math.max(res,room);
            }else{
                int count = check(processing,intervals[i]);
                room -= count;
                room++;
                processing.add(intervals[i]);
                res = Math.max(res,room);
            }
        }
        return res;
    }
    
    private int check(List<int[]> processing, int[] interval){
        int count = 0;
        Iterator<int[]> iterator = processing.iterator();
        while(iterator.hasNext()){
            int[] temp = iterator.next();
            if(temp[1] <= interval[0]){
                count++;
                iterator.remove();
            }
        }
        return count;
    }
}
// approach 1 using min-heap
class Solution {
    public int minMeetingRooms(int[][] intervals) {
        
    // Check for the base case. If there are no intervals, return 0
    if (intervals.length == 0) {
      return 0;
    }

    // Min heap
    PriorityQueue<Integer> allocator = new PriorityQueue<Integer>(); 

    // Sort the intervals by start time
    Arrays.sort(
        intervals,
        new Comparator<int[]>() {
          public int compare(final int[] a, final int[] b) {
            return a[0] - b[0];
          }
        });

    // Add the first meeting
    allocator.add(intervals[0][1]);

    // Iterate over remaining intervals
    for (int i = 1; i < intervals.length; i++) {

      // If the room due to free up the earliest is free, assign that room to this meeting.
      if (intervals[i][0] >= allocator.peek()) {
        allocator.poll();
      }

      // If a new room is to be assigned, then also we add to the heap,
      // If an old room is allocated, then also we have to add to the heap with updated end time.
      allocator.add(intervals[i][1]);
    }

    // The size of the heap tells us the minimum rooms required for all the meetings.
    return allocator.size();
  }
}

思路二: Chronological Ordering。这是lc的approach 2,也是discussion forum的high votes answer。这是原作者的思路:链接。基本思路是将开始时间和结束时间分别列为两个sorted array。初始化两个指针,start,end。一个指向开始事件,一个指向结束事件。遍历开始数组,如果开始事件小于结束事件,说明前面会议都还没结束的,那么room + 1,开始事件指针+1,但是结束事件指针并不动;否则的话,表明有一个会议结束了,空出来一个房间,room无需+1,结束事件的指针指向下一个事件(+1),开始事件指针也+1。下面展示代码:

public class Solution {
    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;
    }
}

总结:

  1. heap在java中的实现是priority queue。
  2. heap必须是一个完全二叉树,但不要求是满二叉树。
  3. 例如min heap。只要求父节点大于所有的子节点,但是没有规定左右节点谁大谁小。
  4. heap采用顺序存储方式:Leetcode 253 Meeting Rooms II
  5. 循环list并要删除元素的时候应该采用iterator迭代器。