[LeetCode] 2406. Divide Intervals Into Minimum Number of Groups

https://leetcode.com/problems/divide-intervals-into-minimum-number-of-groups/description/?envType=daily-question&envId=2024-10-12

leetcode - Divide Intervals Into Minimum Numbers of Groups

문제 유형: 우선순위 큐, 정렬

문제 난이도: Medium

 

문제

You are given a 2D integer array intervals where intervals[i] = [lefti, righti] represents the inclusive interval [lefti, righti].

You have to divide the intervals into one or more groups such that each interval is in exactly one group, and no two intervals that are in the same group intersect each other.

Return the minimum number of groups you need to make.

Two intervals intersect if there is at least one common number between them. For example, the intervals [1, 5] and [5, 8] intersect.

 

intervals[i] = [left, right]로 이루어진 2D배열을 받습니다.

이 요소들의 수의 범위가 겹치지 않게 최소 그룹을 만드시오.

 

서로 다른 요소간에 right와 left가 겹치면 안됩니다.

 

풀이

https://riveroverflow.tistory.com/entry/LeetCode-1942-The-Number-of-the-Smallest-Unoccupied-Chair

[LeetCode] 1942. The Number of the Smallest Unoccupied Chair

이 문제와 유사하다.

 

우선순위큐를 2개 이용하면 된다.

우선, intervals를 정렬해주면 된다.

그 뒤, {right, 그룹번호}의 최소힙 우선순위큐를 만든다. 이를 pq라 부르겠다.

{그룹번호}의 최소힙 우선순위큐를 만든다. 이를 next라 부르겠다.

 

순차적으로 Intervals배열을 읽으면서, 다음을 계속한다:

pq에 현재 left보다 작은 right 수들을 pop해서, 그 그룹번호만 next에 담는다.

 

만약 next가 비어있다면, {right , (최대그룹번호++)}를 pq에 Push하고,

비어있지 않다면, {right, next의 맨 위값}을 pq에 Push하고 next에서 pop한다.

 

순회를 끝내고, 최대그룹번호를 반환한다.

 

코드

C++

#pragma GCC optimize("03", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    int minGroups(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end());
        int maxGroupNo = 1;
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; //{endtime, groupNo}
        priority_queue<int, vector<int>, greater<int>> next;
        for(const auto &member : intervals) {
            int left = member[0];
            int right = member[1];

            while(!pq.empty() && left > pq.top().first) {
                next.push(pq.top().second);
                pq.pop();
            }

            int groupNo;
            if(!next.empty()) {
                groupNo = next.top();
                next.pop();
            } else {
                groupNo = maxGroupNo++;
            }

            pq.push({right, groupNo});
        }

        return maxGroupNo-1;
    }
};