Java Solution with sort and two pointers


  • 0
    K
    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 i = 0;
        int j = 0;
        int num = 0;
        int result = 0;
        while (i < starts.length) {
            int currentStart = starts[i++];
            num++;
            while (ends[j] <= currentStart) {
                num--;
                j++;
            }
            result = Math.max(result, num);
        }
        return result;
    }
    

    Here is my thinking process: The minimum number of meetings rooms are determined by the ongoing meetings at the same time. Moreover, more meeting rooms are needed when a new meeting cannot fit into an existing room. So I will consider the start time of each interval.

    First I sort all the starts and ends, and use "num" to keep track of the number of meeting rooms needed after each start.

    When every start is processed, we increase num by 1, because we need a new meeting room for this interval. However, this num is not the minimum number of meeting rooms needed at this time, because some meeting rooms can be released if the meeting ends before "currentStart".

    Now "num" records the number of ongoing meetings at the same time, and we update the result.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.