C ++
 Computer >> コンピューター >  >> プログラミング >> C ++

C++で含まれる間隔

各間隔に2つの値[開始、終了]がある間隔の2次元リストがあるとします。別の間隔を含む間隔があるかどうかを確認する必要があります。

したがって、入力が[[2,4]、[5,11]、[5,9]、[10,10]]の場合、[5,11]には[5、 9]。

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

  • 配列を並べ替えるv

  • 1つの2D配列retを定義する

  • 間隔ごとにv−

    • retが空の場合、-

      • retの最後に挿入します

    • それ以外の場合、retの最後の要素> =it [0]の場合、-

      • trueを返す

    • それ以外の場合

      • retの最後に挿入します

  • falseを返す

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

例 

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   bool static cmp(vector<int> &a, vector<int> &b) {
      return a[1] == b[1] ? a[0] > b[0] : a[1] < b[1];
   }
   bool solve(vector<vector<int>> &v) {
      sort(v.begin(), v.end(), cmp);
      vector<vector<int>> ret;
      for (auto &it : v) {
         if (ret.empty())
         ret.push_back(it);
         else if (ret.back()[0] >= it[0])
         return true;
         else
         ret.push_back(it);
      }
      return false;
   }
};
main() {
   Solution ob;
   vector<vector<int>> v = {{2,4},{5,11},{5,9},{10,10}};
   cout << (ob.solve(v));
}

入力

{{2,4},{5,11},{5,9},{10,10}}

出力

1

  1. C++でゲームVをジャンプする

    arrと呼ばれる整数の配列と整数dがあるとします。 1つのステップで、インデックスiから-にジャンプできます。 i + xここで、i +x

  2. C++での区間リストの共通部分

    閉じた区間のリストが2つあるとします。ここでは、区間の各リストはペアごとに互いに素であり、ソートされた順序になっています。これら2つの間隔リストの共通部分を見つけました。 閉区間[a、b]はa<=bとして表されることがわかっています。 a <=x<=bの実数xのセット。 2つの閉じた区間の共通部分は、空であるか、閉じた区間として表すことができる実数のセットです。 したがって、入力がA =[[0,2]、[5,10]、[13,23]、[24,25]]およびB =[[1,5]、[8,12]、[ 15,24]、[25,27]]の場合、出力は[[1,2]、[5,5]、[8,10]、[15,23]、[