LeetCode Find Right Interval

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]的结果。

代码如下:

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;
	}
};

本代码提交AC,用时299MS。

上述代码还可优化,在已排序区间数组中找第一个start大于j的区间时,可以用二分搜索。

另外因为所有区间的start不相同,所以事先用hash记录start和原数组下标。这样只需要把所有区间的start抽出来排序,然后二分查找每一个end。代码如下:

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;
	}
};

本代码提交AC,用时96MS,快了不少。

Leave a Reply

Your email address will not be published. Required fields are marked *