LeetCode Find Right Interval Given a set of intervals, for each of the interval i, check if there exists an interval j whose start point is bigger than or equal to the end point of the interval i, which can be called that j is on the “right” of i. For any interval i, you need to store the minimum interval j’s index, which means that the interval j has the minimum start point to build the “right” relationship for interval i. If the interval j doesn’t exist, store -1 for the interval i. Finally, you need output the stored value of each interval as an array. Note:

1. You may assume the interval’s end point is always bigger than its start point.
2. You may assume none of these intervals have the same start point.

Example 1:

Input: [ [1,2] ]
Output: [-1]
Explanation: There is only one interval in the collection, so it outputs -1.

Example 2:

Input: [ [3,4], [2,3], [1,2] ]
Output: [-1, 0, 1]
Explanation: There is no satisfied "right" interval for [3,4].
For [2,3], the interval [3,4] has minimum-"right" start point;
For [1,2], the interval [2,3] has minimum-"right" start point.

Example 3:

Input: [ [1,4], [2,3], [3,4] ]
Output: [-1, 2, -1]
Explanation: There is no satisfied "right" interval for [1,4] and [3,4].
For [2,3], the interval [3,4] has minimum-"right" start point.

---

给定一系列区间[start,end]，定义区间[i,j]的“右区间”为[u,v]使得u是第一个不小于j的数。要求输出每个区间的右区间下标，如果不存在右区间，则输出-1。 我的解法。因为要输出右区间在原数组中的下标，所以得保留每个区间在原数组中的下标。定义一个新的结构体MyInterval，用来保存区间以及该区间在原数组中的下标。对所有区间按start排序，然后遍历每一个区间[i,j]，在已排序区间数组中找第一个start大于j的区间，取出它的下标作为区间[i,j]的结果。 代码如下： [cpp] typedef struct MyInterval { Interval inter; int idx; MyInterval(Interval inter_, int idx_) :inter(inter_), idx(idx_) {}; bool operator<(const MyInterval& myi) const{ return this->inter.start < myi.inter.start; // 所有start不相同 } }; class Solution2 { public: vector<int> findRightInterval(vector<Interval>& intervals) { int n = intervals.size(); vector<MyInterval> myvs; for (int i = 0; i < n; ++i) { MyInterval myint(intervals[i], i); myvs.push_back(myint); } sort(myvs.begin(), myvs.end()); vector<int> ans(n, -1); for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { // 线性查找 if (myvs[j].inter.start >= myvs[i].inter.end) { ans[myvs[i].idx] = myvs[j].idx; break; } } } return ans; } }; [/cpp] 本代码提交AC，用时299MS。 上述代码还可优化，在已排序区间数组中找第一个start大于j的区间时，可以用二分搜索。 另外因为所有区间的start不相同，所以事先用hash记录start和原数组下标。这样只需要把所有区间的start抽出来排序，然后二分查找每一个end。代码如下： [cpp] class Solution { private: int binsearch(const vector<int>& starts, int target) { int l = 0, r = starts.size() – 1; while (l <= r) { int m = l + (r – l) / 2; if (starts[m] == target)return starts[m]; if (starts[m] < target)l = m + 1; else r = m – 1; } return starts[l]; } public: vector<int> findRightInterval(vector<Interval>& intervals) { int n = intervals.size(); vector<int> starts; unordered_map<int, int> hash; for (int i = 0; i < n; ++i) { starts.push_back(intervals[i].start); hash[intervals[i].start] = i; } sort(starts.begin(), starts.end()); vector<int> ans(n, -1); for (int i = 0; i < n; ++i) { if (intervals[i].end <= starts[n – 1]) { int t = binsearch(starts, intervals[i].end); ans[i] = hash[t]; } } return ans; } }; [/cpp] 本代码提交AC，用时96MS，快了不少。]]>