区块链技术博客
www.b2bchain.cn

253.会议室II

这篇文章主要介绍了253.会议室II的讲解,通过具体代码实例进行22900 讲解,并且分析了253.会议室II的详细步骤与相关技巧,需要的朋友可以参考下https://www.b2bchain.cn/?p=22900

本文实例讲述了2、树莓派设置连接WiFi,开启VNC等等的讲解。分享给大家供大家参考文章查询地址https://www.b2bchain.cn/7039.html。具体如下:

253.会议室II

文章目录

  • 题目分析
  • Solution – 最小堆
  • Solution – 分开排序

题目分析

  • 按照常识,要根据开始时间来排序,先开的排在前面
  • 前面有会议开完,则可以利用该会议室;否则,要新开一间会议室

Solution – 最小堆

253.会议室II

  • 最小堆,取最小值:O(1);插入,删除:O(logn)
  • 堆顶:最早开的会的结束时间,这样要开的会的开始时间最早结束的会议的结束时间比较
  • 最后堆中,剩下的元素个数为所需要的会议室,即没有在要开的会了
public int minMeetingRooms(int[][] intervals) {     if (intervals == null || intervals.length == 0) return 0;      // 按照会议的开始时间,从小到大排序  nlogn     Arrays.sort(intervals, (m1, m2) -> m1[0] - m2[0]);      // 创建一个最小堆(存放每一个会议的结束时间)     PriorityQueue<Integer> heap = new PriorityQueue<>();     // 添加0号会议的结束时间     heap.add(intervals[0][1]);      // 堆顶的含义:目前占用的会议室中最早结束的时间     for (int i = 1; i < intervals.length; i++) { // nlogn         // i号会议的开始时间 >= 堆顶         if (intervals[i][0] >= heap.peek()) {             heap.remove();         }         // 将i号会议的结束时间加入堆中         heap.add(intervals[i][1]);     }     return heap.size(); } 

Solution – 分开排序

253.会议室II

  • 开始时间排序 –> 最小堆前的排序 –> 即按照会议开始时间排序
  • 结束时间排序 –> 最小堆排序 –> 目前最早结束时间
    public int minMeetingRooms(int[][] intervals) {         if (intervals == null || intervals.length == 0) return 0;         // 存放所有会议的开始时间         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;         for (int begin : begins) {             if (begin >= ends[endIdx]) { // 能重复利用会议室                 endIdx++;             } else { // 需要新开一个会议室                 room++;             }         }          return room;     } 

Reference:小码哥MJ

本文转自互联网,侵权联系删除253.会议室II

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » 253.会议室II
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们