程序查找挂起C ++中所有横幅所需的最小针数

假设我们有一个[[开始，结束]]形式的间隔列表，它表示我们要悬挂的横幅的开始和结束点。悬挂横幅至少需要一根大头针，一根横幅可以悬挂多个横幅。我们必须找到悬挂所有标语所需的最少针数。

因此，如果输入的间隔是= [[2，5]，[5，6]，[8，10]，[10，13]]，那么输出将为2，因为我们可以将两个引脚放置在5和10悬挂所有横幅。

为了解决这个问题，我们将遵循以下步骤-

• 根据时间间隔的结束值对数组v排序

• ret：= 0

• 最后：= -inf

• 对于v中的每个项目-

• 忽略以下部分，跳至下一个迭代

• 如果最后> =开始，则-

• （增加ret 1）

• 最后：=结束

• 返回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