文档章节

436. Find Right Interval

大兔崽子
 大兔崽子
发布于 05/09 14:42
字数 354
阅读 5
收藏 0

Problem

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:

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

Solution

Use brute force. Use a vector “a” as a bitmap to check whether the given number is the lower bound of an interval. If a[i] is -1, the interval with the lower bound of i does not exist, and if a[i] is not -1, the interval with the lower bound of i exists and its index in the given vector “intervals” is a[i].

Code

class Solution {
public:
    vector<int> findRightInterval(vector<vector<int>>& intervals) {
        vector<int> ret;
        int size = intervals.size();
        int min = 2147483647; 
        int max = -2147483648;
        for (int i = 0; i < size; i++) 
        {
            ret.push_back(-1);
            if (intervals[i][0] > max)
            {
                max = intervals[i][0];
            }
            if (intervals[i][0] < min)
            {
                min = intervals[i][0];
            }
        }
        
        int len = max - min + 1;
        int *a = new int[len];
        memset(a, -1, sizeof(int) * len);
        for (int i = 0; i < size; i++)
        {
            a[intervals[i][0] - min] = i;
        }
        int j = 0;
        for (auto i = 0; i < size; i++)
        {
            for (j = intervals[i][1] - min; j < len; j++)
            {
                if (a[j] != -1)
                {
                    ret[i] = a[j];
                    break;
                }
            }
        }
        return ret;
    }
};

504 Love u

© 著作权归作者所有

大兔崽子
粉丝 1
博文 27
码字总数 24376
作品 0
杭州
私信 提问
echart如何做到多个datazoom时间轴拖动同步

各位: 请问大家有没有遇到这这样的需求:一个页面上有多个chart 图,并且每个chart的时间轴拖动事件要同步,即:一个chart的时间轴在拖动,页面上其他chart的时间轴也跟随的变化。请问 大家...

zxmin
2016/11/18
1K
0
找到start比区间i的end大或相等的一个区间 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, wh......

叶枫啦啦
2018/01/04
10
0
横向柱状图手机端,点击最后一个柱子,其他的全部消失

@Kener-林峰 你好,想跟你请教个问题,我在手机端写的横向柱状图,都是动态获取数据,点击最后一个其他的全部消失,请问这是什么原因呢? 点击最后一个柱子后,显示 代码: var color = ['rg...

soumns-
2017/06/06
87
1
上下滚动播报特效

html: <div style="height:50px;overflow:hidden;font-size: 14px;font-weight: bold;"> <ul class="line"> <li style="line-height:25px;"> <span class="glyphicon glyphicon-hand-right"......

hming
2016/11/28
10
0
Visifire 2.2.0 正式版发布

Visifire 是一个基于SilverLight的 Chart组件,VISIFire 公司提供了 Open Source 的 Silverlight 2 Chart 组件,遵循GPL v3,可以在 ASP, ASP.Net, PHP, JSP, CodeFusion, Ruby on Rails 以及......

红薯
2009/05/17
259
0

没有更多内容

加载失败,请刷新页面

加载更多

你知道多少this,new,bind,call,apply?那我告诉你

那么什么是this,new,bind,call,apply呢?这些你都用过吗?掌握这些内容都是基础中的基础了。如果你不了解,那还不赶快去复习复习,上网查阅资料啥的! 通过call,apply,bind可以改变thi...

达达前端小酒馆
今天
5
0
设计模式之命令模式

命令模式的类图 其中的角色有: Client 客户端。只依赖于调用者Invoker、接收者Receiver、以及Command(网上找的图片这里没有画出来),不用关注接收者如何执行命令,只需要告诉调用者需要执行...

陈年之后是青葱
今天
7
0
2. 彤哥说netty系列之IO的五种模型

你好,我是彤哥,本篇是netty系列的第二篇。 欢迎来我的公从号彤哥读源码系统地学习源码&架构的知识。 简介 本文将介绍linux中的五种IO模型,同时也会介绍阻塞/非阻塞与同步/异步的区别。 何...

彤哥读源码
今天
5
0
OSChina 周四乱弹 —— 喵的波粒二象性

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @ 小小编辑推荐:《水墨兰亭》- 李志辉 《水墨兰亭》- 李志辉 手机党少年们想听歌,请使劲儿戳(这里) @巴拉迪维 :卧室里采光要足够好,这样...

小小编辑
今天
37
1
前后端分离接口规范

最近在开发,遇到前后端关于Boolean类型的参数传参和接收的问题: 场景:后台会根据用户是否出车/是否出司机(Boolean类型)来决定后端的业务逻辑(比如费用的计算),前端使用JSON字符串类型...

code-ortaerc
昨天
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部