leetcode253. 会议室 II(mid)

解题思路

代码(优先队列)复杂度代码(有序化)复杂度
力扣链接

官方题解

优先队列
有序化
代码(优先队列)

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        //按照开始时间进行排序
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));

        //构建小顶堆
        PriorityQueue pq = new PriorityQueue<>();

        //将第一场会议的结束时间添加到堆顶
        pq.offer(intervals[0][1]);

        //如果当前会议的开始时间>=堆中最小的会议结束时间,对应元素弹出
        for (int i = 1; i < intervals.length; ++i) {
            if (intervals[i][0] >= pq.peek()) {
                pq.poll();
            }
            pq.offer(intervals[i][1]);
        }
        //pq中元素剩余的元素大小就是需要的会议室数量
        return pq.size();
    }
}

class Solution {
    //有序化
    public int minMeetingRooms(int[][] 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][0];
            end[i] = intervals[i][1];
        }

        //对开始时间和结束时间排序
        Arrays.sort(start);
        Arrays.sort(end);

        //需要使用的会议室数量
        int rooms = 0;

        //分别指向开始时间和结束时间数组的当前位置
        int sp = 0;
        int ep = 0;
        while (sp < n) {
            //此时有会议结束了,空出一间会议室,rooms - 1,ep + 1
            if (start[sp] >= end[ep]) {
                rooms -= 1;
                ep += 1;
            }

            //使用一间会议室,romms + 1,sp + 1
            rooms += 1;
            sp += 1;
        }
        
        return rooms;
    }
}