Skip to main content

1353 - Maximum Number of Events That Can Be Attended

info

풀이 키워드​

스포주의

정렬 그리디 힙


풀이 코드​

info
  • 메모리: 76130 KB
  • 시간: 63 ms
class Solution {
    public int maxEvents(int[][] events) {
        // sort by start day
        Arrays.sort(events, (a, b) -> a[0] - b[0]);

        // sort by end day
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        int n = events.length;
        int idx = 0;
        int today = 1;
        int ans = 0;
        while (idx < n || !pq.isEmpty()) {
            // more events upcoming but none exists for today
            if (pq.isEmpty()) today = events[idx][0];

            // can attend today
            while (idx < n && events[idx][0] <= today) {
                pq.add(events[idx++][1]); // sort by end day
            }

            pq.poll(); // attend
            ++ans;
            ++today; // set to next day

            // remove expired events
            while (!pq.isEmpty() && pq.peek() < today) {
                pq.poll();
            }
        }

        return ans;
    }
}

풀이 해설​

여러 이벤트의 start day, end day가 주어지고, 하루 당 이벤트 하나씩만 참여 가능할 때,

참여할 수 있는 최대 이벤트 수를 구하는 문제이다.

이는 전형적인 그리디 유형으로 정렬 기준이 2가지이므로

start day로 오름차순 정렬 한 번 거친 후 end day를 기준으로 최소힙을 사용하면 된다.


tip

조건 설계 시 보이는 패턴​

while 문에 들어가는 condition 중 반복되는 패턴을 소개한다.

1️⃣ isEmpty() 外 추가 요구사항​

큐가 비어있을때 정말 끝내도 되는지 한번 더 생각해보자.

이 문제에선 큐가 비어도 아직 남은 이벤트가 존재할 수 있기에 추가 조건이 요구된다.

while (idx < n || !pq.isEmpty())

2️⃣ IOOB Exception 유도형​

인덱스가 condition에 사용될 경우, bound check를 선행하고 논리 AND로 연결하자.

// can attend today
while (idx < n && events[idx][0] <= today)

3️⃣ NPE 유도형​

peek() 자체적으론 문제 없지만 null < int 구문에서 NPE가 발생한다.

따라서 empty check를 선행하고 논리 AND로 연결하자.

// remove expired events
while (!pq.isEmpty() && pq.peek() < today)

🗒️ 풀이 템플릿​

모든 그리디 문제에 해당하는 것은 아니고,
정렬 + 그리디 + 힙 유형의 문제에서 대부분 이런식으로 풀이했다.

  1. 기준 1로 정렬
  2. 각 시점마다 선택 가능한 원소를 힙에 추가
  3. 기준 2가 가장 임박한 원소를 선택 👉️ 최선의 선택지이자 그리디적인 판단
  4. 다음 시점에서 만료되는 원소를 힙에서 제거
  5. 모든 원소를 확인할 때까지 step 2 ~ 4 반복

📚 유사 문제​


메모​

  • 연습할땐 꽤 자주 보이는 그리디 유형. 근데 실전에서 나올진 몰?루