解題說明
Find Right Interval
題目描述：給定 intervals[i] = [startᵢ, endᵢ]（所有 startᵢ 唯一）。對每個區間 i，找「右區間」——滿足 startⱼ ≥ endᵢ 且 startⱼ 最小的區間 j，回傳其原始索引；不存在則回傳 -1。
解題思路：
核心觀察：每個區間的 start 值唯一，可建立 map<int,int> startToIdx，將 start 值對應到其原始索引。
對每個區間 i，需要找最小的 start ≥ end[i]，這正是 lower_bound(end[i]) 的用途：
- 若
lower_bound找到結果（it != map.end()），則it->second就是右區間的原始索引。 - 若找不到（已超過所有 start），則答案為 -1。
建圖時間 O(n log n)，查詢每個區間 O(log n)，整體 O(n log n)。
C++ 解法
複雜度分析
時間複雜度：O(n log n) — 建立 map 需 O(n log n)；對每個區間做一次 lower_bound 為 O(log n)，共 O(n log n)。
空間複雜度：O(n) — map 儲存 n 個 (start, index) 對。
虛擬碼
1. Build startToIdx map: for each i, startToIdx[intervals[i].start] = i 2. For each interval i: a. end = intervals[i].end b. it = startToIdx.lower_bound(end) c. if it == end of map: result.push(-1) d. else: result.push(it->second) 3. Return result
其他解法
排序 + 二分搜尋陣列：將所有 (start, index) 對存入陣列並排序，對每個 end 用 std::lower_bound 搜尋——效果相同，但排序步驟更顯式，適合對 map 不熟悉時使用。
暴力法 O(n²)：對每個區間 i，線性掃描所有其他區間找最小的 start ≥ end[i]——簡單但在 n 大時超時，僅適合理解問題。
雙指針排序法 O(n log n)：分別按 end 和 start 排序兩個副本，用雙指針從左到右配對——常數因子略小，但需要額外記錄原始索引映射。
延伸思考
- 若 start 值不唯一（允許多個區間有相同 start），如何修改解法？
- 若需同時找「左區間」（最大的 startⱼ ≤ startᵢ），map 的哪個操作可完成此任務？
- 此問題與「會議室」問題（Meeting Rooms）有何結構上的相似性？