題目: LeetCode - 436. Find Right Interval
題目說明
給一堆區間,求每個區間的最近右邊區間的索引號 ( 右邊區間的 start >= 左邊區間的 end),若不存在則為 -1。
解題思路
使用 map 紀錄每個區間的起始點及索引號,接著遍歷所有區間,使用 lower_bound()
實現二分查找。
參考解法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
| static auto __ = []() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); return 0; }(); class Solution { public: vector<int> findRightInterval(vector<vector<int>>& intervals) { vector<int> v; map<int, int> m; auto iter = m.begin(); for(int i = 0; i < intervals.size(); ++i) m[intervals[i][0]] = i; for(auto& interval : intervals) v.emplace_back((iter = m.lower_bound(interval[1])) != m.end() ? iter->second : -1); return v; } };
|