在 C++ 中查找正确区间

c++server side programmingprogramming

假设我们有区间，对于每个区间 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 := 区间数组的大小，创建大小为 n 的数组 ret，并使用 -1 填充，创建一个名为 m 的映射
对于 i 在 0 到区间大小的范围内
- 如果 intervals[i, 0] 在 m 中，则跳到下一个区间
- m[intervals[i, 0]] := i + 1
对于 i 在 n 范围内 – 1 向下到 i >= 0
- it := 指向具有最小键但不小于 intervals[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));
}