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

  • Z时代
  • 2024-01-10
  • 分类：综合

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

因此，如果输入的间隔是= [[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

    以上是 程序查找挂起C ++中所有横幅所需的最小针数 的全部内容， 来源链接： utcz.com/z/350132.html

    回到顶部