C++에서 올바른 간격 찾기

a 구간이 있다고 가정하고 구간 i 각각에 대해 시작점이 구간 i의 끝점보다 크거나 같은 구간 j가 있는지 확인합니다. j는 i의 "오른쪽"에 있다고 합니다. 모든 구간 i에 대해 최소 구간 j의 인덱스를 저장해야 합니다. 이는 구간 j가 구간 i에 대한 "올바른" 관계를 구축하기 위한 최소 시작점이 있음을 나타냅니다. 구간 j가 존재하지 않으면 구간 i에 대해 -1을 저장합니다. 그리고 마지막으로 각 구간의 저장된 값을 배열로 출력해야 합니다. 따라서 입력이 [[3,4], [2,3], [1,2]]와 같으면 출력은 [-1, 0, 1]이 됩니다. , 4], 간격 [2,3]의 경우 간격 [3,4]에는 최소 "오른쪽" 시작점이 있습니다. 그리고 [1,2]의 경우 간격 [2,3]에는 최소 "오른쪽" 시작점이 있습니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• n :=간격 배열의 크기, 크기가 n인 am 배열 ret를 만들고 -1을 사용하여 채우고 m

  이라는 맵을 만듭니다.

• 범위 0에서 간격 크기까지의 i에 대해

  • 간격[i, 0]이 m이면 다음 간격으로 건너뜁니다.

  • m[간격[i, 0]] :=i + 1

• 범위 n – 1에서 i>=0

  까지 i에 대해

  • it :=가장 작은 키를 갖지만 간격[i, 1]

    보다 작지 않은 키-값 쌍을 가리킵니다.

  • 값이 0이면 다음 반복으로 이동합니다.

  • ret[i] :=그것의 값 – 1

• 리턴 렛

예시(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]