Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 풀어보는 참석 가능한 최대 이벤트 수: 그리디 + 우선순위 큐 완전 정복

문제 개요

events[i] = [startDayi, endDayi] 형태의 이벤트 배열이 주어진다고 가정해 봅시다. i번째 이벤트는 startDayi에 시작하여 endDayi에 종료되며, d가 startDayi부터 endDayi 사이(양 끝 포함)에 있는 임의의 날짜에 해당 이벤트에 참석할 수 있습니다. 단, 같은 날에는 하나의 이벤트만 참석 가능하다는 조건이 있습니다. 우리의 목표는 참석할 수 있는 이벤트의 최대 개수를 구하는 것입니다.

예를 들어, 입력이 [[1,4], [4,4], [2,2], [3,4], [1,1]]이라면 출력은 4가 됩니다. [1, 1], [2, 2], [3, 4], [4, 4] 네 개의 이벤트에 모두 참석할 수 있기 때문입니다.

접근 방법: 그리디 전략과 우선순위 큐

이 문제는 그리디(Greedy) 전략과 우선순위 큐(Priority Queue)를 함께 사용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 “종료일이 가장 빠른 이벤트를 우선적으로 처리한다”는 것입니다.

해결 과정을 단계별로 살펴보면 다음과 같습니다.

  • n := 이벤트의 개수로 설정하고, 이벤트 목록을 시작일(start day) 기준으로 오름차순 정렬합니다. ret := 0, itr := 0으로 초기화합니다.
  • 최소 힙(min-heap) 기반의 우선순위 큐 pq를 생성합니다. 이렇게 하면 종료일이 가장 빠른 이벤트가 항상 top에 위치하게 됩니다.
  • i를 1부터 100000까지 순회하며 아래 작업을 반복합니다.
    • itr < n이면서 events[itr][0] == i인 동안, pq에 events[itr][1](종료일)을 삽입하고 itr을 1 증가시킵니다.
    • pq가 비어 있지 않으면서 pq의 top이 i보다 작은 동안, 이미 종료된 이벤트이므로 pq에서 해당 요소를 제거합니다.
    • pq가 비어 있지 않다면 pq에서 하나를 꺼내고 ret을 1 증가시킵니다. 이는 i번째 날에 종료일이 가장 빠른 이벤트에 참석했다는 의미입니다.
  • 모든 순회가 끝나면 ret을 반환합니다.

왜 최소 힙(min-heap)을 사용할까?

특정 날짜에 참석 가능한 이벤트가 여러 개라면, 종료일이 가장 가까운 이벤트를 먼저 선택하는 것이 유리합니다. 종료일이 늦은 이벤트는 나중에 참석할 기회가 더 많기 때문입니다. C++에서는 priority_queue를 선언할 때 세 번째 템플릿 인자로 greater<int>를 전달하여 최소 힙으로 구성할 수 있습니다.

C++ 구현 예제

다음 구현을 통해 더 자세히 이해해 봅시다 −

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    static bool cmp(vector<int>& a, vector<int>& b){
        return a[0] < b[0];
    }
    int maxEvents(vector<vector<int>>& events) {
        int n = events.size();
        sort(events.begin(), events.end(), cmp);
        int ret = 0;
        int itr = 0;
        priority_queue<int, vector<int>, greater<int>> pq;
        for(int i = 1; i <= 1e5; i++){
            while(itr < n && events[itr][0] == i){
                pq.push(events[itr][1]);
                itr++;
            }
            while(!pq.empty() && pq.top() < i) pq.pop();
            if(!pq.empty()){
                pq.pop();
                ret++;
            }
        }
        return ret;
    }
};
main(){
    vector<vector<int>> v = {{1,4},{4,4},{2,2},{3,4},{1,1}};
    Solution ob;
    cout << (ob.maxEvents(v));
}

입력

[[1,4],[4,4],[2,2],[3,4],[1,1]]

출력

4

복잡도 분석

  • 시간 복잡도: O(D + N log N). 여기서 D는 날짜 순회 범위(최대 105), N은 이벤트의 개수입니다. 각 이벤트는 우선순위 큐에 한 번 삽입되고 한 번 제거되므로, 힙 연산의 총 비용은 O(N log N)입니다.
  • 공간 복잡도: O(N). 우선순위 큐에 동시에 저장될 수 있는 요소의 최대 개수는 이벤트 수 N을 초과하지 않습니다.