Leetcode #253. Meeting Rooms II

Genius Solution:

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        int rooms = 0;
        if (intervals == null || intervals.length == 0 || intervals[0].length == 0) return rooms;
        int[] starts = new int[intervals.length];
        int[] ends = new int[intervals.length];

        for(int i = 0; i < intervals.length; i++) {
            starts[i] = intervals[i][0];
            ends[i] = intervals[i][1];
        }

        Arrays.sort(starts);
        Arrays.sort(ends);

        int endsItr = 0;
        for (int i = 0; i < starts.length; i++) {
            if (starts[i] < ends[endsItr]) rooms++;
            else endsItr++;
        }

        return rooms;
    }
}

reference: https://leetcode.com/problems/meeting-rooms-ii/discuss/67855/Explanation-of-%22Super-Easy-Java-Solution-Beats-98.8%22-from-%40pinkfloyda

Another MinHeap method:

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        int rooms = 0;
        if (intervals == null || intervals.length == 0 || intervals[0].length == 0) return rooms;

        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] a, int[] b) {return a[0] - b[0];}
        });

        PriorityQueue<int[]> heap = new PriorityQueue<int[]>(intervals.length, new Comparator<int[]>() {
            public int compare(int[] a, int[] b) {return a[1] - b[1];}
        });

        heap.offer(intervals[0]);

        for (int i = 1; i < intervals.length; i++) {
        // get the meeting room that finishes earliest
        int[] interval = heap.poll();

        if (intervals[i][0] >= interval[1]) {
            // if the current meeting starts right after 
            // there's no need for a new room, merge the interval
            interval[1] = intervals[i][1];
        } else {
            // otherwise, this meeting needs a new room
            heap.offer(intervals[i]);
        }

        // don't forget to put the meeting room back
        heap.offer(interval);
    }

    return heap.size();
    }
}

yokostan / Leetcode-Solutions

Leetcode #253. Meeting Rooms II #232