[코테연습] 2054. Two Best Non-Overlapping Events

문제 타입

• 구간 문제 (Interval Problem)
  • 두 개의 겹치지 않는 구간을 선택하여 최대 값을 구하는 문제.
• 동적 계획법 (Dynamic Programming)
  • 이전 상태(구간의 최대 값)를 저장하며 최적의 결과를 도출.
• 정렬 기반 탐색 (Sort-based Search)
  • 이벤트의 종료 시간을 기준으로 정렬 후 탐색.

---

문제 분석

• 입력:
  • events: 각 이벤트는 [start, end, value] 형태의 리스트로 주어짐.
• 목표:
  • 두 개의 겹치지 않는 이벤트를 선택하여 value의 합이 최대가 되는 경우를 반환.
• 조건:
  • 이벤트가 겹치지 않으려면, 첫 번째 이벤트의 종료 시간 end가 두 번째 이벤트의 시작 시간 start보다 작아야 함.
• 제약:
  • 시간 복잡도를 O(n2)O(n^2)O(n2)보다 효율적으로 만들어야 함.
• 접근 전략:
  1. 이벤트를 종료 시간을 기준으로 정렬해 구간을 효율적으로 탐색.
  2. 이전까지의 최대 값을 저장하며 각 이벤트에 대해 최적의 값을 계산.

---

문제 풀이

풀이 과정

1. 이벤트 정렬:
   • 종료 시간 기준으로 events를 정렬해 효율적 탐색 가능하도록 준비.
2. 이전 최대 값 추적:
   • SortedDict(Python) 또는 TreeMap(Java)을 활용해 특정 시점 이전까지의 최대 값을 저장.
   • 이 구조를 통해 빠르게 "겹치지 않는 가장 큰 값"을 가져올 수 있음.
3. 최대 값 계산:
   • 각 이벤트를 순회하면서:
     • 현재 이벤트 이전에 종료된 이벤트의 최대 값을 가져옴.
     • 현재 이벤트와 이전 값의 합을 계산해 최대 값 갱신.
   • best_previous_value를 업데이트하며 현재까지의 최대 값을 저장.
4. 결과 반환:
   • 두 개의 겹치지 않는 이벤트의 최대 합을 반환.

 

 

> java

 

import java.util.*;

class Solution {
    public int maxTwoEvents(int[][] events) {
        // 종료 시간을 기준으로 정렬
        Arrays.sort(events, (a, b) -> Integer.compare(a[1], b[1]));

        int maxValue = 0;
        int bestPreviousValue = 0;
        TreeMap<Integer, Integer> map = new TreeMap<>(); // 종료 시점과 그때의 최대 value 저장

        for (int[] event : events) {
            int start = event[0];
            int end = event[1];
            int value = event[2];

            // 현재 이벤트 이전에 종료된 이벤트의 최대 값을 가져옴
            Map.Entry<Integer, Integer> entry = map.floorEntry(start - 1);
            int nonOverlappingValue = entry == null ? 0 : entry.getValue();

            // 현재 이벤트와 이전의 최대 값을 합산
            maxValue = Math.max(maxValue, value + nonOverlappingValue);

            // 현재까지의 최대 값을 갱신
            bestPreviousValue = Math.max(bestPreviousValue, value);
            map.put(end, bestPreviousValue);
        }

        return maxValue;
    }
}

 

> python

 

from sortedcontainers import SortedDict

class Solution:
    def maxTwoEvents(self, events: List[List[int]]) -> int:
         # 종료 시간을 기준으로 정렬
        events.sort(key=lambda x: x[1])
        
        max_value = 0
        best_previous_value = 0
        sorted_map = SortedDict()  # 종료 시점과 그때의 최대 value 저장
        
        for start, end, value in events:
            # 현재 이벤트 이전에 종료된 이벤트의 최대 값을 가져옴
            keys = sorted_map.keys()
            index = sorted_map.bisect_left(start) - 1
            non_overlapping_value = sorted_map[keys[index]] if index >= 0 else 0
            
            # 현재 이벤트와 이전의 최대 값을 합산
            max_value = max(max_value, value + non_overlapping_value)
            
            # 현재까지의 최대 값을 갱신
            best_previous_value = max(best_previous_value, value)
            sorted_map[end] = best_previous_value
        
        return max_value