Meeting Room Allocation Problem

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

 

Leetcode의 meeting room #2 문제이다.

 

문제확인을 위해 유료결제가 필요하지만 그냥 구글링해서 문제를 긁어왔다. 실습시간에도 사용된 문제이니 함 풀어보자

 

meeting.cpp

0.00MB

 

 

1. C++

쉬운 줄 알고 아래처럼 풀었는데,

쉽지 않았다..

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>


// 요런게 Main 문제로 여겨진다.

using namespace std;

// Function to find the minimum number of meeting rooms required
int minMeetingRooms(vector<pair<int, int> >& intervals) {
    //////////////
    // FILL HERE
    int ans = 1;
    int n = intervals.size();
    sort(intervals.begin(),intervals.end());

    for(int i=0;i<n;i++){
        auto temp = intervals[i];
        int cnt = 1;
        for(int j=i+1;j<n;j++){
            if(intervals[j].second<=temp.first || intervals[j].first>=temp.second) continue;
            else cnt++;
        }
        ans = max(ans,cnt);
    }

    return ans;
}

int main() {
    // Example input: pair of <start_time, end_time>
    vector<pair<int, int> > intervals;
    intervals.push_back(make_pair(0, 30));
    intervals.push_back(make_pair(5, 20));
    intervals.push_back(make_pair(15, 35));

    vector<pair<int, int> > intervals2;
    intervals2.push_back(make_pair(7, 10));
    intervals2.push_back(make_pair(2, 4));

    vector<pair<int, int> > intervals3;
    intervals3.push_back(make_pair(0, 30));
    intervals3.push_back(make_pair(5, 10));
    intervals3.push_back(make_pair(15, 20));

    // Find the minimum number of meeting rooms required
    int result = minMeetingRooms(intervals);
    int result2 = minMeetingRooms(intervals2);
    int result3 = minMeetingRooms(intervals3);

    cout << "Minimum number of meeting rooms required: " << result << endl; // expected : 3
    cout << "Minimum number of meeting rooms required: " << result2 << endl; // expected : 1
    cout << "Minimum number of meeting rooms required: " << result3 << endl; // expected : 2

    return 0;
}

보다시피

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

위 Code론 위 case에서 2를 출력하지 못하고 3을 출력한다. 너무 단순하게 생각했나보다.

 

좀 더 사고해보자

 

이렇게 정렬을 begin 기준 반대로 해주면 test case 3번처럼 포괄(?)적인 case를 처리할 수 있다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

// Function to find the minimum number of meeting rooms required
int minMeetingRooms(vector<pair<int, int> >& intervals) {
    //////////////
    // FILL HERE
    int ans = 1;
    int n = intervals.size();
    sort(intervals.rbegin(),intervals.rend());

    for(int i=0;i<n;i++){
        auto temp = intervals[i];
        int cnt = 1;
        for(int j=i+1;j<n;j++){
            if(intervals[j].second<=temp.first || intervals[j].first>=temp.second) continue;
            else cnt++;
        }
        ans = max(ans,cnt);
    }

    return ans;
}

int main() {
    // Example input: pair of <start_time, end_time>
    vector<pair<int, int> > intervals;
    intervals.push_back(make_pair(0, 30));
    intervals.push_back(make_pair(5, 20));
    intervals.push_back(make_pair(15, 35));

    vector<pair<int, int> > intervals2;
    intervals2.push_back(make_pair(7, 10));
    intervals2.push_back(make_pair(2, 4));

    vector<pair<int, int> > intervals3;
    intervals3.push_back(make_pair(0, 30));
    intervals3.push_back(make_pair(5, 10));
    intervals3.push_back(make_pair(15, 20));

    // Find the minimum number of meeting rooms required
    int result = minMeetingRooms(intervals);
    int result2 = minMeetingRooms(intervals2);
    int result3 = minMeetingRooms(intervals3);

    cout << "Minimum number of meeting rooms required: " << result << endl; // expected : 3
    cout << "Minimum number of meeting rooms required: " << result2 << endl; // expected : 1
    cout << "Minimum number of meeting rooms required: " << result3 << endl; // expected : 2

    return 0;
}

결론 제시한 코드로 정답 도출에는 문제가 없습니다. 그러나 O(n2)O(n^2)O(n2)의 시간 복잡도는 대규모 입력에서 매우 느릴 수 있습니다. 효율성이 중요하지 않은 상황에서는 이 방식도 허용 가능합니다.

 

 

그렇지만,, GPT 문의해보니 정석은 Heap 구조로 푸는 것이었다.

 

    sort(intervals.begin(),intervals.end());
    priority_queue<int,vector<int>,greater<int>> minheap;
    minheap.push(intervals[0].second);

    for(int i=1;i<intervals.size();i++){
        if(intervals[i].first>=minheap.top()) minheap.pop();
        minheap.push(intervals[i].second);
    }
    return minheap.size();