ค้นหาช่วงเวลาที่เหมาะสมใน C++

สมมติว่าเรามีช่วง a สำหรับแต่ละช่วง i ให้ตรวจสอบว่ามีช่วง j ที่มีจุดเริ่มต้นมากกว่าหรือเท่ากับจุดสิ้นสุดของช่วง i หรือไม่ ซึ่งสามารถทำได้ เรียกว่า j อยู่ทาง "ขวา" ของ i สำหรับช่วงเวลา i ใดๆ เราต้องเก็บดัชนีช่วงเวลาต่ำสุดของ j ซึ่งระบุว่าช่วงเวลา j มีจุดเริ่มต้นต่ำสุดเพื่อสร้างความสัมพันธ์ "ถูกต้อง" สำหรับช่วงเวลา i เมื่อไม่มีช่วง j ให้เก็บ -1 สำหรับช่วงเวลา i และสุดท้าย เราต้องการเอาท์พุตค่าที่เก็บไว้ของแต่ละช่วงเวลาเป็นอาร์เรย์ ดังนั้นหากอินพุตเป็น [[3,4], [2,3], [1,2]] ดังนั้นเอาต์พุตจะเป็น [-1, 0, 1] เนื่องจากไม่มีช่วงที่เหมาะสมดังกล่าวสำหรับ [3 , 4], สำหรับช่วง [2,3] ช่วง [3,4] มีจุดเริ่มต้นต่ำสุด-"ขวา"; และสำหรับ [1,2] ช่วงเวลา [2,3] จะมีจุดเริ่มต้นต่ำสุด-"ขวา"

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• n :=ขนาดของช่วงเวลาอาร์เรย์ สร้าง am array ret ขนาด n แล้วเติมโดยใช้ -1 ให้สร้างแผนที่ที่เรียกว่า m

• สำหรับฉันอยู่ในช่วง 0 ถึงขนาดของช่วงเวลา

  • หากช่วงเวลา[i, 0] เป็น m ให้ข้ามไปยังช่วงถัดไป

  • ม[ช่วงเวลา[i, 0]] :=ผม + 1

• สำหรับผมอยู่ในช่วง n – 1 ลงไปที่ i>=0

  • it :=ชี้ไปที่คู่คีย์-ค่าที่มีคีย์ที่เล็กที่สุด แต่ไม่เล็กกว่า intervals[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]