Programming

  1. Meeting Rooms II

By PattySung 26 December 2023
Meeting Rooms II

Given an array of meeting time intervals intervals where intervals[i] = [starti, endi], return the minimum number of conference rooms required.

Example 1:

Input: intervals = [[0,30],[5,10],[15,20]] Output: 2 Example 2:

Input: intervals = [[7,10],[2,4]] Output: 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;
    }
}

Time: O(nlogn)

<解法二>int[][]


class Solution {
    public int minMeetingRooms(int[][] intervals) {
        if (intervals == null || intervals.length == 0){
            return 0;
        }
    
    Arrays.sort(intervals, (a, b) -> (a[0] - b[0]));
    PriorityQueue<Integer> heap = new PriorityQueue<>();

    for (int[] interval : intervals){
        if (heap.size() > 0 && heap.peek() <= interval[0]){
            heap.poll();
        }       
        heap.offer(interval[1]);
    }
    return heap.size();
    }
}