LeetCode - 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

제약사항

1 <= intervals.length <= 104
0 <= starti < endi <= 106

Solution

[전략]
1. 2차원 input array의 시작시간과 끝나는 시간을 각각 배열에 저장한다.
2. 각 배열을 오름차순으로 sort
3. 배열을 순회하면서 i번째 미팅이 시작할때

• a. 가장 빠른 끝나는 시간보다 시작시간이 더 전이면 room을 추가한다.
• b. 가장 빠른 끝나는 시간보다 시작시간이 더 이후이면 room은 추가하지 않고(끝난 room에서 할수있으므로) 다음 가장 빠른 끝나는 시간으로 index를 이동한다.

import java.util.*;

class Solution {
    public int minMeetingRooms(int[][] intervals) {

        int numOfIntervals = intervals.length;

        int[] startPoints = new int[numOfIntervals];
        int[] endPoints = new int[numOfIntervals];

        for (int i = 0; i < numOfIntervals; i++) {
            startPoints[i] = intervals[i][0];
            endPoints[i] = intervals[i][1];
        }

        Arrays.sort(startPoints);
        Arrays.sort(endPoints);

        int numOfRooms = 0;
        int endPointIdx = 0;
        for (int i = 0; i < numOfIntervals; i++) {

            if (startPoints[i] < endPoints[endPointIdx]) {
                numOfRooms++;
            } else {

                endPointIdx++;
            }
        }
        return numOfRooms;

    }
}