[LeetCode 436.] Find Right Interval

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了[LeetCode 436.] Find Right Interval，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3037字，纯文字阅读大概需要5分钟。

内容图文

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

内容总结

以上是互联网集市为您收集整理的[LeetCode 436.] Find Right Interval全部内容，希望文章能够帮你解决[LeetCode 436.] Find Right Interval所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---