[JAVA 문제 풀이] 366. Maximum Number of Events That Can Be Attended [참석할 수 있는 최대 이벤트 수]

Maximum Number of Events That Can Be Attended - LeetCode

Can you solve this real interview question? Maximum Number of Events That Can Be Attended - You are given an array of events where events[i] = [startDayi, endDayi]. Every event i starts at startDayi and ends at endDayi. You can attend an event i at any day d where startTimei <= d <= endTimei. You can only attend one event at any time d. Return the maximum number of events you can attend.   Example 1: [https://assets.leetcode.com/uploads/2020/02/05/e1.png] Input: events = [[1,2],[2,3],[3,4]] Output: 3 Explanation: You can attend all the three events. One way to attend them all is as shown. Attend the first event on day 1. Attend the second event on day 2. Attend the third event on day 3. Example 2: Input: events= [[1,2],[2,3],[3,4],[1,2]] Output: 4   Constraints: * 1 <= events.length <= 105 * events[i].length == 2 * 1 <= startDayi <= endDayi <= 105

https://leetcode.com/problems/maximum-number-of-events-that-can-be-attended/description/

events[i] = [startDayi, endDayi]의 다양한 이벤트가 주어집니다.
모든 events[i]는 startDay[i]에서 시작하여 endDay[i]에서 끝납니다.

eventi는 startTimei <= d <= endTimei인 d에서 언제든지 참석할 수 있습니다.
eventi는 언제든지 한 번만 참석할 수 있습니다.

참석할 수 있는 최대 이벤트 수를 반환합니다.

제약 조건:
* 1 <= events.length <= 105
* events[i]length == 2
* 1 <= startDayi <= endDayi <= 105

내가 작성한 코드

import java.util.*;

class Solution {
    public int maxEvents(int[][] events) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(); // 이벤트를 종료일 기준으로 관리하는 큐
        int day = 1; // 현재 날짜
        int idx = 0; // 이벤트 인덱스
        int answer = 0; // 참석한 이벤트 수

        // 이벤트를 시작일 기준으로 정렬
        Arrays.sort(events, (a, b) -> a[0] - b[0]);

        // day는 최소 시작일 ~ 최대 종료일까지 순회
        while (idx < events.length || !pq.isEmpty()) {

            // 오늘 시작되는 이벤트들을 우선순위 큐에 넣음 (endDay 기준)
            while (idx < events.length && events[idx][0] == day) {
                pq.offer(events[idx][1]);
                idx++;
            }

            // 이미 끝난 이벤트는 큐에서 제거
            while (!pq.isEmpty() && pq.peek() < day) {
                pq.poll();
            }

            // 오늘 참석할 수 있는 이벤트 하나 선택
            if (!pq.isEmpty()) {
                pq.poll(); // 가장 빨리 끝나는 이벤트 참석
                answer++;
            }

            day++; // 다음 날로 이동
        }

        return answer;
    }
}

다른 사람의 코드

import java.util.*;

class Solution {
    public int maxEvents(int[][] events) {
        // 이벤트들을 끝나는 날짜 오름차순으로 정렬
        Arrays.sort(events, (a, b) -> a[1] - b[1]);

        // 날짜별 사용할 수 있는 가장 빠른 날을 저장할 배열 생성
        // 가장 마지막으로 시작하는 이벤트의 끝나는 날짜 + 2 크기로 초기화
        int[] root = new int[events[events.length - 1][1] + 2];

        // Union-Find 초기화: 자기 자신을 부모로 초기화
        for (int i = 0; i < root.length; i++)
            root[i] = i;

        int res = 0; // 참석한 이벤트 수

        // 각 이벤트를 순회
        for (int[] e : events) {
            // 해당 이벤트가 시작할 수 있는 가장 빠른 날짜를 찾음
            int availableSlot = find(root, e[0]);

            // 만약 찾은 날짜가 이벤트의 끝나는 날짜 이하라면
            if (availableSlot <= e[1]) {
                res++; // 참석 가능하므로 결과 증가

                // 이 날짜는 사용되었으므로, root[availableSlot]을 다음 날짜로 연결
                root[availableSlot] = find(root, availableSlot + 1);
            }
        }

        return res;
    }

    // Union-Find의 find 연산: 현재 날짜 i에서 사용 가능한 가장 빠른 날짜 찾기
    public int find(int[] root, int i) {
        if (root[i] != i)
            root[i] = find(root, root[i]); // 경로 압축 (Path Compression)
        return i;
    }
}

Union-Find (서로소 집합) - stupefyee

기술정리

https://stupefyee.inblog.io/unionfind-%EC%84%9C%EB%A1%9C%EC%86%8C-%EC%A7%91%ED%95%A9--61568