題目描述:給定 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 就是右區間的原始索引。建圖時間 O(n log n),查詢每個區間 O(log n),整體 O(n log n)。
時間複雜度: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 排序兩個副本,用雙指針從左到右配對——常數因子略小,但需要額外記錄原始索引映射。