Find Right Interval ใน C++ : หา Interval ที่เริ่มต้นขวาสุด

ให้ Array ของ **Intervals** intervals[i] = [start, end] สำหรับแต่ละ Interval i หา **Index j** ที่:

• intervals[j][0] >= intervals[i][1] (Start ของ j อยู่ขวา/เท่ากับ End ของ i)
• intervals[j][0] **น้อยที่สุด** ที่สatisfy เงื่อนไข (Right-most interval ที่เริ่มต้นเร็วที่สุด)
• ถ้าไม่มี -> -1

ตัวอย่าง

Input:  [[3,4], [2,3], [1,2]]
Interval 0: [3,4] -> ไม่มี Start >= 4 -> -1
Interval 1: [2,3] -> Start >= 3 คือ [3,4] (Index 0) -> 0
Interval 2: [1,2] -> Start >= 2 คือ [2,3] (Index 1) -> 1

Output: [-1, 0, 1]

แนวทาง: Map + Lower Bound (O(N log N))

1. สร้าง map (Map เรียง Key เอง) — เก็บ **Start ที่ไม่ซ้ำ** (First Occurrence)
2. สำหรับแต่ละ Interval i (วนย้อนหลังหรือไปหน้าก็ได้):
   • it = m.lower_bound(intervals[i][1]) -> Iterator แรกที่ Key >= End
   • ถ้า it != m.end() -> ret[i] = it->second
   • Else -> -1

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<int> findRightInterval(vector<vector<int>>& intervals) {
        int n = intervals.size();
        vector<int> ret(n, -1);
        map<int, int> m; // start -> index (first occurrence)

        // Build map: only first occurrence of each start
        for (int i = 0; i < n; i++) {
            if (!m.count(intervals[i][0]))
                m[intervals[i][0]] = i;
        }

        // Query for each interval
        for (int i = n - 1; i >= 0; i--) {
            auto it = m.lower_bound(intervals[i][1]);
            if (it != m.end())
                ret[i] = it->second;
        }
        return ret;
    }
};

Input / Output

Input:  [[3,4],[2,3],[1,2]]
Output: [-1,0,1]

ความซับซ้อน (Complexity)

• Time: O(N log N) — Map Insert + Lower Bound ต่อ Interval
• Space: O(N) — Map + Result

หมายเหตุ

Map รองรับ Duplicate Start โดยเก็บ Index แรกสุด (Smallest Index) ซึ่งตรงกับโจทย์ที่ต้องการ Minimum Start (และถ้า Start เท่ากัน Index น้อยกว่าก็ดี) ครับ