在C ++中找到正确的时间间隔

假设我们有一个区间，对于每个区间i，检查是否存在一个区间j，其起点大于或等于区间i的终点，可以称j在区间i的“右边”一世。对于任何间隔i，我们都必须存储最小间隔j的索引，这表明间隔j具有最小起点，可以为间隔i建立“正确”关系。当间隔j不存在时，则为间隔i存储-1。最后，我们需要将每个间隔的存储值作为数组输出。因此，如果输入类似于[[3,4]，[2,3]，[1,2]]，则输出将为[-1、0、1]，因为对于[3]没有这样的间隔，，4]，对于间隔[2,3]，间隔[3,4]具有最小的“右”起始点；对于[1,2]，间隔[2,3]具有最小值-“右”

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

• n：= interval数组的大小，创建大小为n的am ret，然后使用-1填充，创建一个名为m的映射

• 对于范围在0到区间大小的i

• 如果interval [i，0]以m为单位，则跳到下一个间隔

• m [intervals [i，0]]：= i + 1

• 对于范围在n – 1到i> = 0的i

• ：=指向键值对，键对值最小，但不小于interval [i，1]

• 如果它的值为0，则进行下一次迭代

• ret [i]：=它的值– 1

• 返回ret

范例（C ++）

让我们看下面的实现以更好地理解-

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
public:
   vector<int> findRightInterval(vector<vector<int>>& intervals) {
      int n = intervals.size();
      vector <int> ret(n, -1);
      map <int, int< m;
      for(int i = 0; i < intervals.size(); i++){
         if(m.count(intervals[i][0])) continue;
         m[intervals[i][0]] = i + 1;
      }
      for(int i = n - 1; i >= 0; i--){
         map <int, int> :: iterator it = m.lower_bound(intervals[i][1]);
         if(it->second == 0) continue;
         ret[i] = it->second - 1;
      }
      return ret;
   }
};
main(){
   vector<vector<int>> v = {{3,4},{2,3},{1,2}};
   Solution ob;
   print_vector(ob.findRightInterval(v));
}

输入值

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

输出结果

[-1,0,1]