LeetCode 436. Find Right Interval

一道需要自定义比较函数的二分查找题。

题目描述

You are given an array of intervals, where intervals[i] = [starti, endi] and each starti is unique.

The right interval for an interval i is an interval j such that startj >= endi and startj is minimized.

Return an array of right interval indices for each interval i. If no right interval exists for interval i, then put -1 at index i.

Example 1:

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

Example 2:

Input: intervals = [[3,4],[2,3],[1,2]]
Output: [-1,0,1]
Explanation: There is no right interval for [3,4].
The right interval for [2,3] is [3,4] since start0 = 3 is the smallest start that is >= end1 = 3.
The right interval for [1,2] is [2,3] since start1 = 2 is the smallest start that is >= end2 = 2.

Example 3:

Input: intervals = [[1,4],[2,3],[3,4]]
Output: [-1,2,-1]
Explanation: There is no right interval for [1,4] and [3,4].
The right interval for [2,3] is [3,4] since start2 = 3 is the smallest start that is >= end1 = 3.

Constraints:

• 1 <= intervals.length <= 2 * 104
• intervals[i].length == 2
• -106 <= starti <= endi <= 106
• The start point of each interval is unique.

解题思路

题目限定了每个时间段的开始时间是唯一的，让我们去找每个结束时间之后的下一个最早的开始时间。
我们可以首先按开始时间进行排序，然后对于每个结束时间，使用二分查找找出开始时间即可。
这里，下一个开始时间可以和当前结束时间相同，所以选用的应该是 lower_bound。
我们可以自定义比较器，根据 cplusplus.com 所说，This can either be a function pointer or a function object。也就是说我们可以传入一个比较函数，或者手写一个 struct 并重载 () 运算符，当然我们也可以直接使用 lambda。
cppreference.com 给出了比较器中参数类型的对应关系：

• 第一个参数是容器元素类型；
• 第二个参数是目标元素类型；
  为什么要区分两种不同类型呢，因为我们这两种元素可以是不同类型的，如本题中我们的 target 是一个 int，而 element 是 pair<int,int> 或者 vector<int>。

参考代码

lambda写法直接在行内写函数体，比较紧凑，类型也容易对应：

/*
 * @lc app=leetcode id=436 lang=cpp
 *
 * [436] Find Right Interval
 */

// @lc code=start
class Solution {
public:
    vector<int> findRightInterval(vector<vector<int>>& intervals) {
        assert(!intervals.empty());

        size_t n = intervals.size();
        vector< pair<int,int> > v(n);
        for (int i=0; i<n; i++) {
            v[i] = { intervals[i][0], i };
        }
        sort(v.begin(), v.end());
        vector<int> res(n);
        for (int i=0; i<n; i++) {
            auto it = lower_bound(v.begin(), v.end(), intervals[i][1],
                [&](const pair<int,int>& p, const int& target){ return p.first < target; });
            if (it != v.end()) {
                res[i] = it->second;
            } else {
                res[i] = -1;
            }
        }
        return res;
    } // AC
};
// @lc code=end

或者使用比较函数和比较器，这里只给出需要修改的部分代码：

// 比较函数写法：
    static bool cmp(const pair<int,int>& p, const int& target){
        return p.first < target;
    }
    auto it = lower_bound(v.begin(), v.end(), intervals[i][1], cmp); // AC

// 比较器写法：
    struct comp {
        bool operator()(const pair<int,int>& p, const int& target) {
            return p.first < target;
        }
    };
    auto it = lower_bound(v.begin(), v.end(), intervals[i][1], comp()); // AC