253.会议室2

253.会议室

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

示例：
输入：[[0,30],[5,10],[15,20]]
输出：2

思路一：最小堆
给定一组会议时间，求最少需要开启多少间会议室能满足需要； 首先要对数组按开始时间做升序排序；其次需要一个数据结构来存储开启的会议；这里考虑用最小堆 (PriorityQueue) 来实现，因为最小堆查最小值得复杂度是O(1)

时间复杂度:   O(nlogn)
空间复杂度：O(n)

   public int minMeetingRooms(int[][] intervals) {
       //0.边界处理
       if(intervals==null||intervals.length==0) return 0;

       //1. 按照会议开始时间，升序排列 O(nlongn)
       Arrays.sort(intervals,(m1,m2)->m1[0]-m2[0]);
    
       //2. 创建最小堆(存放每一个会议的结束时间)
       PriorityQueue<Integer> heap = new PriorityQueue();
       //添加0号会议的结束时间
       heap.add(intervals[0][1]);

       //3. 遍历会议数组 求得需要开启的会议室间数
       for(int i = 1; i < intervals.length();i++) { //O(nlogn)

          /** 
          如果当前会议的开始时间 大于等于 最近会议的结束时间; 
          那就把最近会议移除 然后把当前会议的结束时间加最小堆 堆顶
          */
          if(intervals[I][0] >= heap.peek()) {//O(1)
             heap.remove(); //O(logn)
          }
          //将i号会议的结束时间加入堆中
          heap.add(intervals[i][1]);  //O(logn)
       }

       return heap.size();
    
   }
     

 思路二： 分开排序
 把开始时间做一个排序，再把结束时间做一个排序；遍历开始时间数组，取出每一个开始时间对比结束时间，看是否需要开启新的房间

     
     时间复杂度:   O(nlogn)
   空间复杂度：O(n)

   public int minMeetingRooms(int[][] intervals) {
       //0.边界处理
       if(intervals==null||intervals.length==0) return 0;

       //1. 创建两个数组分别记录开始和结束时间
       int[] begins = new int[intervals.length];
       int[] ends = new int[intervals.length];
       for(int i = 0;i < intervals.length;i++){
           begins[i] = intervals[i][0];
           ends[i] = intervals[i][1];
       }
       //排序
       Arrays.sort(begins);
       Arrays.sort(ends);

       int room = 0, endIdx = 0;
       //2. 遍历会议开始时间
       for(int begin : begins) {
           //可以重复利用会议室
           if(begin >= ends[endIdx]) {
               endIdx++;
           }else {//需要新开会议室
              room++;
           }
       }
       return room;
   }

     
    ```