[LeetCode] Maximum Number Of Events That Can Be Attended

문제는 다음과 같다.


LeetCode Maximum Number Of Events That Can Be Attended

이벤트가 빨리 끝나는 순으로 정렬도 해 보았고, 이벤트가 짧은 순으로도 정렬을 해보며 다양하게 삽질을 했던 문제다. 시간 초과가 나지 않도록 O(n)의 시간 복잡도로 해결하기 위해 많은 고민을 했다.

1. 이벤트가 시작되는 순서를 기준으로 올림차순으로 정렬한다
2. 포인터를 0일차부터 하루씩 나아가며 시작일이 포인터와 같아진다면, 달라질 때까지 우선순위 큐에 종료일을 넣는다.
3. 다음 시작일을 만날 때까지 하루에 하나씩 우선순위 큐에서 값을 꺼낸다.
4. 단, 꺼낸 값이 포인터보다 작다면 무시한다.(선택받지 못한 이벤트)

현재에서 가장 최선의 값을 선택하다보면 해결할 수 있는 그리디 알고리즘이었지만, 이런 생각을 하기까지 정말 오랜 시간이 걸렸다.

import java.util.*;

class Solution {
    public int maxEvents(int[][] events) {
        int cnt = 0, idx = 0, tmp;
        Arrays.sort(events, (a, b) -> a[0] - b[0]);
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        int pos = 0;
        while (idx < events.length) {
            pos = events[idx][0];
            while (idx < events.length && events[idx][0] == pos) {
                pq.add(events[idx++][1]);
            }
            while(idx < events.length && !pq.isEmpty() && events[idx][0] > pos) {
                tmp = pq.poll();
                if (tmp >= pos) {
                    pos++;
                    cnt++;
                }
            }
        }
        while(!pq.isEmpty()) {
            tmp = pq.poll();
            if (tmp >= pos) {
                pos++;
                cnt++;
            }
        }
        return cnt;
    }
}