C++で参加できるイベントの最大数を求めるアルゴリズム

イベントの配列 events が与えられ、各要素は events[i] = [startDay_i, endDay_i] という形式で表されます。イベント i は startDay_i に始まり、endDay_i に終わります。イベント i には、startDay_i から endDay_i までの範囲(両端の日を含む)の任意の日 d に参加することができます。

ただし、同じ日に参加できるイベントは1つだけという重要な制約があります。この条件のもとで、参加できるイベントの最大数を求めましょう。

例えば、入力が [[1,4], [4,4], [2,2], [3,4], [1,1]] の場合、出力は 4 となります。[1,1]、[2,2]、[3,4]、[4,4] の4つのイベントに参加できるためです。

解法のアプローチ

この問題は、貪欲法と優先度付きキュー(最小ヒープ)を組み合わせることで効率的に解くことができます。基本的な考え方は、「各日に参加可能なイベントの中から、終了日が最も早いものを優先的に選ぶ」というものです。終了日が早いイベントから処理することで、後日に参加できる選択肢を最大限に残せます。

具体的には、以下の手順で解いていきます。

• イベントの総数を n とし、イベントのリストを開始日の昇順でソートします。答えを格納する ret を 0、次に処理するイベントを指すインデックス itr を 0 で初期化します。
• 終了日を管理するための最小ヒープ型の優先度付きキュー pq を作成します。
• i を 1 から 100000 まで繰り返します。
  • itr が n 未満かつ events[itr][0] が i と等しい間、events[itr][1](終了日)を pq に挿入し、itr を1増やします。
  • pq が空でなく、pq の先頭の値が i より小さい(すでに終了しているイベント)間、pq から要素を削除します。
  • pq が空でなければ、先頭の要素を1つ削除し、ret を1増やします(その日に1つのイベントに参加したことを意味します)。
• 最後に ret を返します。

C++による実装例

理解を深めるために、以下の実装例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   static bool cmp(vector <int>& a, vector <int>& b){
      return a[0] < b[0];
   }
   int maxEvents(vector<vector<int>>& events) {
      int n = events.size();
      sort(events.begin(), events.end(), cmp);
      int ret = 0;
      int itr = 0;
      priority_queue <int, vector <int>, greater <int>> pq;
      for(int i = 1; i <= 1e5; i++){
         while(itr < n && events[itr][0] == i){
            pq.push(events[itr][1]);
            itr++;
         }
         while(!pq.empty() && pq.top() < i) pq.pop();
         if(!pq.empty()){
            pq.pop();
            ret++;
         }
      }
      return ret;
   }
};
main(){
   vector<vector<int>> v = {{1,4},{4,4},{2,2},{3,4},{1,1}};
   Solution ob;
   cout << (ob.maxEvents(v));
}

入力

[[1,4],[4,4],[2,2],[3,4],[1,1]]

出力

4

計算量の評価

イベントのソートに O(n log n)、日付ごとのループとヒープ操作全体で O(D log n)(D は最大日数、n はイベント数)の時間計算量となります。ヒープには同時に開いているイベントの終了日のみが保持されるため、メモリ使用量も効率的です。