문제 링크

내 코드

해설 참고.

class Solution {
public:
    int maxTwoEvents(vector<vector<int>>& events) {
        sort(begin(events), end(events), [](vector<int>& e1, vector<int>& e2) {
            return e1[1] < e2[1];
        });
        map<int, int, greater<int>> m;
        m.emplace(0, 0); // {회의 종료 시간, 비용 합}

        int answer{};
        for(auto event : events) {
            auto it = m.lower_bound(event[0] - 1); // 시작시간보다 먼저 마친 마지막 회의

            int newValue = it->second + event[2];
            m.emplace(event[1], newValue);
            answer = max(answer, newValue);
        }

        return answer;
    }
};

생각해보니.. 이 아이디어는 아니더라 ㅋㅋㅋㅋ

Solution

Approach 1: Top-down Dynamic Programming

• 142ms, 155.36MB
• Complexity
  • Let $n$ be the number of events in the events array.
  • Time Complexity: $O(n \cdot \log n)$
  • Space Complexity: $O(n)$

class Solution {
public:
    int maxTwoEvents(vector<vector<int>>& events) {
        sort(events.begin(), events.end());
        vector<vector<int>> dp(events.size(), vector<int>(3, -1));
        return findEvents(events, 0, 0, dp);
    }
    // Recursive function to find the greatest sum for the pairs.
    int findEvents(vector<vector<int>>& events, int idx, int cnt,
                   vector<vector<int>>& dp) {
        if (cnt == 2 || idx >= events.size()) return 0;
        if (dp[idx][cnt] == -1) {
            int end = events[idx][1];
            int lo = idx + 1, hi = events.size() - 1;
            while (lo < hi) {
                int mid = lo + ((hi - lo) >> 1);
                if (events[mid][0] > end)
                    hi = mid;
                else
                    lo = mid + 1;
            }
            int include =
                events[idx][2] + (lo < events.size() && events[lo][0] > end
                                      ? findEvents(events, lo, cnt + 1, dp)
                                      : 0);
            int exclude = findEvents(events, idx + 1, cnt, dp);
            dp[idx][cnt] = max(include, exclude);
        }
        return dp[idx][cnt];
    }
};

GPT

아래 코드는 최대 두 개의 겹치지 않는 이벤트를 선택했을 때 얻을 수 있는 최대 가치합을 구하는 풀이 방법 중 하나를 구현한 예시입니다. 이 코드는 재귀(백트래킹)와 메모이제이션(동적 계획법, DP)을 조합해서 문제를 해결합니다.

코드 개요:

• 이벤트 배열 events는 [시작시간, 종료시간, 가치] 형태로 주어집니다.
• 먼저 events를 정렬합니다. 기본 정렬은 첫 번째 원소(시작시간)를 기준으로 오름차순 정렬합니다.
• maxTwoEvents 함수에서 findEvents 함수를 호출하여 0번 인덱스 이벤트부터 시작하고, 아직 선택한 이벤트 수가 0개인 상태로 탐색을 시작합니다.
• findEvents 함수는 현재 인덱스 idx의 이벤트를 포함할지 말지 결정하고, 그에 따라 최대 가치합을 반환합니다. 최대 2개의 이벤트를 선택할 수 있으므로 cnt는 0, 1, 2 중 하나를 의미하며, 2가 되면 더 이상 이벤트를 선택할 수 없습니다.

자세한 동작 설명:

1. 정렬:

   sort(events.begin(), events.end());

   events를 시작 시간을 기준으로 정렬합니다. 이로 인해 이벤트를 순회할 때, 시작 시간이 점점 증가하는 순서로 검사할 수 있게 됩니다.

2. dp 배열:

   vector<vector<int>> dp(events.size(), vector<int>(3, -1));

   dp[idx][cnt]는 “현재 idx번째 이벤트를 고려할 때, 이미 cnt개의 이벤트를 선택한 상태에서 얻을 수 있는 최대 가치합”을 저장합니다.

   • 여기서 cnt는 0 또는 1일 수 있습니다. (2 이상이면 이미 최대 개수 선택이므로 0 반환)
   • -1은 아직 계산되지 않은 상태를 의미합니다.

3. 재귀 함수 findEvents:

   int findEvents(vector<vector<int>>& events, int idx, int cnt, vector<vector<int>>& dp)

   • idx: 현재 고려 중인 이벤트의 인덱스
   • cnt: 현재까지 선택한 이벤트 수 (0 또는 1)
   • 반환값: 현재 상태에서 얻을 수 있는 최대 가치합

   동작 과정:

   • 기저 조건:

     if (cnt == 2 || idx >= events.size()) return 0;

     만약 이미 2개 이벤트를 골랐거나, 더 이상 볼 이벤트가 없다면 가치합을 0으로 반환합니다. (더 이상 선택 불가)

   • 메모이제이션 확인:

     if (dp[idx][cnt] != -1) return dp[idx][cnt];

     만약 dp[idx][cnt]에 이미 값이 계산되어 있다면 재계산하지 않고 그 값을 반환합니다.

   • 현재 이벤트를 선택하는 경우(include): 현재 이벤트 events[idx]의 종료 시간 end를 얻습니다.

     int end = events[idx][1];

     이 이벤트를 선택한다면, 이 이벤트와 겹치지 않는 다음 이벤트를 찾아야 합니다. 겹치지 않는 다음 이벤트란 “시작 시간이 현재 이벤트의 종료 시간보다 큰” 이벤트 중 가장 앞서는 이벤트를 의미합니다.

     이를 위해 이진 탐색을 사용합니다:

     int lo = idx + 1, hi = events.size() - 1;
     while (lo < hi) {
         int mid = lo + ((hi - lo) >> 1);
         if (events[mid][0] > end)
             hi = mid;
         else
             lo = mid + 1;
     }

     위 이진 탐색은 lo가 “현재 이벤트 종료 시간보다 큰 시작 시간을 가진 이벤트”를 가리키도록 합니다. 이 시점에서 lo 위치의 이벤트가 end보다 큰 시작 시간을 가진 가장 앞선 이벤트가 됩니다(또는 배열 끝에 도달).

     이제 include 값은 현재 이벤트 가치(events[idx][2]) + 다음 겹치지 않는 이벤트부터 얻을 수 있는 최대 가치합이 됩니다.

     int include = events[idx][2] 
                   + ((lo < events.size() && events[lo][0] > end) 
                       ? findEvents(events, lo, cnt + 1, dp) 
                       : 0);

     여기서 cnt + 1은 이번 이벤트를 선택했으니 선택 수를 1 증가시킨 것입니다.

   • 현재 이벤트를 선택하지 않는 경우(exclude): 이벤트 idx를 건너뛰고 idx + 1번째 이벤트부터 고려합니다. 이때 선택한 이벤트 수 cnt는 변화 없습니다.

     int exclude = findEvents(events, idx + 1, cnt, dp);

   • include와 exclude 중 더 큰 값을 dp[idx][cnt]에 저장합니다.

     dp[idx][cnt] = max(include, exclude);

4. 결과 반환: 최종적으로 findEvents(events, 0, 0, dp) 호출 결과가 최대 두 개의 이벤트를 선택했을 때 얻을 수 있는 최대 가치합이 됩니다.

정리:

• 이 코드는 재귀+메모이제이션 방식을 사용해서 최대 2개의 비겹치는 이벤트를 선택하는 문제를 풀고 있습니다.
• 각 단계에서 이벤트를 “포함”하거나 “제외”하는 두 가지 선택을 하고, 포함하는 경우에는 겹치지 않는 다음 이벤트를 이진 탐색으로 찾아 효율적으로 넘어갑니다.
• dp 배열을 이용하여 중복 계산을 피합니다.
• 결국, 모든 가능한 조합을 고려하되 DP를 통해 시간 복잡도를 줄여 효율적으로 문제를 해결하는 코드입니다.

Approach 2: Min-heap

• 56ms, 126.12MB
• Complexity
  • Let $n$ be the number of events in the events array.
  • Time Complexity: $O(n \cdot \log n)$
  • Space Complexity: $O(n)$

class Solution {
public:
    int maxTwoEvents(vector<vector<int>>& events) {
        // Create a min-heap to store the ending time with value.
        priority_queue<pair<int, int>, vector<pair<int, int>>,
                       greater<pair<int, int>>>
            pq;
        sort(events.begin(), events.end());

        int maxVal = 0, maxSum = 0;

        for (auto& event : events) {
            // Pop all valid events from queue and take their maximum.
            while (pq.size() && pq.top().first < event[0]) {
                maxVal = max(maxVal, pq.top().second);
                pq.pop();
            }

            maxSum = max(maxSum, maxVal + event[2]);
            pq.push({event[1], event[2]});
        }

        return maxSum;
    }
};

GPT

아래 코드는 최대 두 개의 겹치지 않는 이벤트를 선택했을 때 얻을 수 있는 최대 가치합을 효율적으로 구하는 또 다른 방식의 구현 예시입니다.

코드 개요:

• 이벤트들이 [시작시간, 종료시간, 가치]로 주어질 때, 이 코드에서는 우선 이벤트를 시작 시간 기준으로 정렬합니다.
• 이후 각 이벤트를 순회하면서, 우선순위 큐(최소 힙)을 사용하여 이전에 처리한 이벤트들 중 현재 이벤트와 겹치지 않는(종료 시간이 현재 이벤트 시작 시간보다 먼저 끝난) 이벤트들을 관리합니다.
• 겹치지 않는 이전 이벤트들 중 가장 가치가 높은 이벤트를 추적하면서 현재 이벤트와 조합하여 최대 가치 합을 갱신합니다.

자세한 동작 과정:

1. 정렬:

   sort(events.begin(), events.end());

   이벤트를 시작 시간 기준으로 정렬합니다. 이렇게 하면 이벤트를 순서대로 확인할 때, 새로운 이벤트는 이전 이벤트들보다 항상 같거나 뒤에 시작하게 됩니다.

2. 우선순위 큐 사용(pq):

   priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

   pq는 {종료시간, 가치}를 담은 최소 힙입니다. 종료 시간이 작은 이벤트가 먼저 나오도록 greater<pair<int,int>>를 사용합니다.

   이 우선순위 큐는 “아직 겹칠 수 있는 가능성이 있는 이전 이벤트들”을 관리하는데 쓰이며, 동시에 “이미 처리한 이벤트들 중, 뒤에 추가될 이벤트와 겹치지 않게 될 경우에 대비”해서 저장합니다.

3. 변수 초기화:

   int maxVal = 0, maxSum = 0;

   • maxVal: 현재까지 (완전히 처리하여 큐에서 뺀) 이벤트들 중 가장 가치가 큰 이벤트의 가치
   • maxSum: 최대 두 개 이벤트를 선택했을 때 얻을 수 있는 최대 가치합을 추적하기 위한 변수

4. 이벤트 순회:

   for (auto& event : events) {
       // event: [start, end, value]
       // 현재 이벤트의 시작 시간: event[0]
       // 현재 이벤트의 종료 시간: event[1]
       // 현재 이벤트의 가치: event[2]
   }

   각 이벤트를 처리하기 전에, 현재 이벤트의 시작 시간보다 일찍 끝나는 이벤트들을 pq에서 뽑아냅니다. 이들은 이미 더 이상 뒤 이벤트와 겹칠 일이 없으므로, 그 중 최대 가치 이벤트를 maxVal로 갱신할 수 있습니다.

   while (pq.size() && pq.top().first < event[0]) {
       maxVal = max(maxVal, pq.top().second);
       pq.pop();
   }

   • pq.top().first는 가장 빠르게 끝나는 이벤트의 종료 시간을 의미합니다.
   • pq.top().first < event[0]이면, 이 이벤트는 현재 이벤트와 겹치지 않습니다.
     따라서 이 이벤트의 가치를 고려해 maxVal를 갱신하고 pq에서 제거합니다.
   • 이렇게 반복해서 현재 이벤트와 겹치지 않는 모든 이전 이벤트를 pq에서 빼내고, 그 중 최대 가치를 추려내 maxVal를 업데이트합니다.

5. 현재 이벤트와의 조합 고려: 이제 maxVal는 현재 이벤트와 겹치지 않는 이전 이벤트 중 최대 가치를 가진 이벤트의 가치입니다.
   따라서 현재 이벤트의 가치(event[2])를 더해 최대 합을 갱신할 수 있습니다.

   maxSum = max(maxSum, maxVal + event[2]);

   이렇게 하면 “이전 이벤트 1개 + 현재 이벤트 1개”의 조합으로 얻을 수 있는 최대합이 될 수 있습니다.

6. 현재 이벤트를 큐에 추가: 이제 현재 이벤트를 큐에 넣습니다. 이것은 이후 처리할 이벤트들이 현재 이벤트와의 조합을 고려할 수 있게 하기 위함입니다.

   pq.push({event[1], event[2]});

7. 종료: 모든 이벤트를 처리한 후 maxSum에는 최대 두 개의 비겹치는 이벤트를 선택했을 때의 최대 가치합이 저장됩니다.

   return maxSum;

정리:

• 이벤트를 시작 시간 순으로 처리하면서, 우선순위 큐를 이용해 이전 이벤트들을 관리합니다.
• 현재 이벤트 시작 시간보다 이른 시간에 끝나는 이벤트들을 큐에서 제거하면서, 제거한 이벤트들 중 최대 가치를 기록합니다(maxVal).
• 각 이벤트마다 maxVal + 현재 이벤트 가치로 최대합을 갱신합니다.
• 결국 한 번의 순회로 O(n log n) 내에 답을 구할 수 있습니다(정렬 O(n log n) + 매 이벤트별 우선순위 큐 연산 O(log n)).

Approach 3: Greedy

• 77ms, 142.88MB
• Complexity
  • Let $n$ be the number of events in the events array.
  • Time Complexity: $O(n \cdot \log n)$
  • Space Complexity: $O(n)$

class Solution {
public:
    int maxTwoEvents(vector<vector<int>>& events) {
        vector<array<int, 3>> times;
        for (auto& e : events) {
            // 1 denotes start time.
            times.push_back({e[0], 1, e[2]});
            // 0 denotes end time.
            times.push_back({e[1] + 1, 0, e[2]});
        }
        int ans = 0, maxValue = 0;
        sort(begin(times), end(times));
        for (auto& timeValue : times) {
            // If current time is a start time, find maximum sum of maximum end
            // time till now.
            if (timeValue[1]) {
                ans = max(ans, timeValue[2] + maxValue);
            } else {
                maxValue = max(maxValue, timeValue[2]);
            }
        }
        return ans;
    }
};

GPT

아래 코드는 maxTwoEvents 문제를 해결하기 위한 또 다른 방법으로, 스위프 라인(sweep line) 기법을 사용합니다. 이 방식은 시간축을 따라 이벤트 시작점과 종료점을 처리하며, 종료된 이벤트들의 최대 가치를 추적하여 새로운 이벤트가 시작할 때 최적 조합을 찾는 방식입니다.

코드 동작 설명:

1. 이벤트 시작/종료 시점 마킹:
   각 이벤트에 대해 시작 시간과 종료 시간을 각각 별개의 “타임 포인트(time point)“로 만들어 처리합니다.

   for (auto& e : events) {
       // 시작 시점: 시간 e[0], 1(시작), 가치 e[2]
       times.push_back({e[0], 1, e[2]});
       
       // 종료 시점: 이벤트가 e[1]에 끝나므로 e[1]+1 시점에
       // 이 이벤트를 "완전히 종료"된 것으로 간주.
       // 0(종료), 가치 e[2]
       times.push_back({e[1] + 1, 0, e[2]});
   }

   여기서 주목할 점은 종료 시간을 e[1] + 1로 설정한 것입니다. 이렇게 하면 이벤트가 실제로 끝난 후 다음 시점에 이 이벤트의 가치를 “확정”할 수 있습니다. 이는 “이벤트가 e[1] 시간까지 차지하고 있으니 e[1]+1 시간부터는 다른 이벤트와 겹치지 않는다”는 개념을 반영한 것입니다.

2. 정렬:
   times 배열을 시간 기준으로 정렬합니다. 이렇게 하면 시간 순서대로 시작/종료 이벤트를 처리할 수 있습니다.

3. 스위프 라인 진행:

   int ans = 0, maxValue = 0;
   for (auto& timeValue : times) {
       // timeValue = {시간, 타입(시작1/종료0), 가치}
       
       // 타입이 1이면 "새로운 이벤트 시작"
       // 타입이 0이면 "이벤트 종료 처리"
       
       if (timeValue[1] == 1) {
           // 새로운 이벤트가 시작하는 시점에,
           // 지금까지 종료된 이벤트 중 최대 가치(maxValue)와 현재 이벤트의 가치를 합쳐 최대값 갱신
           ans = max(ans, timeValue[2] + maxValue);
       } else {
           // 이벤트 하나가 완전히 종료되었으니, 이 이벤트의 가치를 maxValue에 반영
           maxValue = max(maxValue, timeValue[2]);
       }
   }

   • 종료점(0)을 만날 때: 이 이벤트의 가치를 maxValue와 비교 및 갱신합니다. 즉, 지금까지 “완전히 끝난” 이벤트들 중 가장 가치가 큰 값을 항상 maxValue에 저장합니다.
   • 시작점(1)을 만날 때: 이미 끝난 이벤트들 중 최대 가치(maxValue)와 현재 시작하는 이벤트의 가치를 합쳐서 ans를 갱신합니다. 여기서 maxValue는 겹치지 않는 이전 이벤트들의 최대 가치이므로, 두 이벤트를 선택했을 때의 가치 합 최대값을 실시간으로 업데이트할 수 있습니다.

4. 결과 반환: 최종적으로 ans에는 최대 두 개의 겹치지 않는 이벤트를 선택했을 때 가능한 최대 가치 합이 저장됩니다.

정리:

• 이 코드는 시작점과 종료점을 별도로 처리하여 시간 순서대로 이벤트를 스캔합니다.
• 종료된 이벤트의 가치 중 최대 값을 추적해두었다가, 새로운 이벤트가 시작할 때 그 최대값과 합쳐 최대 두 이벤트 선택 시의 최대합을 찾습니다.
• 종료 시간을 e[1] + 1로 잡아 이벤트 겹침을 명확히 처리하고, 정렬과 단순 순회로 O(n log n)에 문제를 해결합니다.