C++ですべてのバナーを吊るすのに必要な最小ピン数を見つけるプログラム

[start、end]の形式の間隔のリストがあると仮定します。これは、ハングさせたいバナーの開始点と終了点を表しています。バナーを掛けるには少なくとも1つのピンが必要であり、1つのピンで複数のバナーを掛けることができます。すべてのバナーを吊るすのに必要な最小数のピンを見つける必要があります。

したがって、入力がintervals =[[2、5]、[5、6]、[8、10]、[10、13]]のような場合、2つのピンを所定の位置に配置できるため、出力は2になります。 5と10で、すべてのバナーを吊るします。

これを解決するには、次の手順に従います-

• 間隔の終了値に基づいて配列vを並べ替えます
• ret：=0
• 最後：=-inf
• 各アイテムについてv−
  • 最後の場合>=開始の場合、-
    • 次の部分を無視し、次の反復にスキップします
  • （retを1増やします）
  • 最後：=それの終わり
• return ret

例（C ++）

理解を深めるために、次の実装を見てみましょう-

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   static bool cmp(vector<int>& a, vector<int>& b) {
      return a.back() < b.back();
   }
   int solve(vector<vector<int>>& v) {
      sort(v.begin(), v.end(), cmp);
      int ret = 0;
      int last = -1e8;
      for (auto& it : v) {
         if (last >= it[0]) {
            continue;
         }
         ret++;
         last = it[1];
      }
      return ret;
   }
};
int solve(vector<vector<int>>& intervals) {
   return (new Solution())->solve(intervals);
}
int main(){
   vector<vector<int>> v = {{2, 5},{5, 6},{8, 10},{10, 13}};
   cout << solve(v);
}

入力

{{2, 5},{5, 6},{8, 10},{10, 13}}

出力

2