Tìm khoảng thời gian phù hợp trong C ++

Giả sử chúng ta có một khoảng, với mỗi khoảng i, hãy kiểm tra xem có tồn tại một khoảng j có điểm đầu lớn hơn hoặc bằng điểm cuối của khoảng i hay không, có thể được gọi là j ở "bên phải" của i. Đối với bất kỳ khoảng i nào, chúng ta phải lưu trữ chỉ số của khoảng j tối thiểu, chỉ số này cho biết rằng khoảng j có điểm bắt đầu nhỏ nhất để xây dựng mối quan hệ "đúng" cho khoảng i. Khi khoảng j không tồn tại, thì lưu -1 cho khoảng i. Và cuối cùng, chúng ta cần xuất giá trị được lưu trữ của mỗi khoảng thời gian dưới dạng một mảng. Vì vậy, nếu đầu vào giống như [[3,4], [2,3], [1,2]], thì đầu ra sẽ là [-1, 0, 1], vì không có khoảng đúng như vậy cho [3 , 4], Đối với khoảng [2,3], khoảng [3,4] có điểm bắt đầu cực tiểu- "phải"; Và đối với [1,2], khoảng [2,3] có điểm bắt đầu tối thiểu- "đúng".

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của mảng khoảng, tạo lại mảng am có kích thước n và điền vào giá trị này bằng cách sử dụng -1, đóng một bản đồ có tên m

• cho tôi trong phạm vi từ 0 đến kích thước của khoảng thời gian

  • nếu khoảng [i, 0] tính bằng m thì chuyển sang khoảng tiếp theo

  • m [khoảng [i, 0]]:=i + 1

• đối với tôi trong phạm vi n - 1 xuống đến i> =0

  • it:=trỏ đến cặp khóa-giá trị có khóa nhỏ nhất nhưng không nhỏ hơn khoảng [i, 1]

  • nếu giá trị của nó là 0, thì hãy chuyển sang lần lặp tiếp theo

  • ret [i]:=value of it - 1

• trả lại ret

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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));
}

Đầu vào

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

Đầu ra

[-1,0,1]