• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]LeetCode436.寻找右区间|FindRightInterval

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号:山青咏芝(shanqingyongzhi)
➤博客园地址:山青咏芝(https://www.cnblogs.com/strengthen/
➤GitHub地址:https://github.com/strengthen/LeetCode
➤原文地址:https://www.cnblogs.com/strengthen/p/10334621.html 
➤如果链接不是山青咏芝的博客园地址,则可能是爬取作者的文章。
➤原文已修改更新!强烈建议点击原文地址阅读!支持作者!支持原创!
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

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.

给定一组区间,对于每一个区间 i,检查是否存在一个区间 j,它的起始点大于或等于区间 i 的终点,这可以称为 j 在 i 的“右侧”。

对于任何区间,你需要存储的满足条件的区间 j 的最小索引,这意味着区间 j 有最小的起始点可以使其成为“右侧”区间。如果区间 j 不存在,则将区间 i 存储为 -1。最后,你需要输出一个值为存储的区间值的数组。

注意:

  1. 你可以假设区间的终点总是大于它的起始点。
  2. 你可以假定这些区间都不具有相同的起始点。

示例 1:

输入: [ [1,2] ]
输出: [-1]

解释:集合中只有一个区间,所以输出-1。

示例 2:

输入: [ [3,4], [2,3], [1,2] ]
输出: [-1, 0, 1]

解释:对于[3,4],没有满足条件的“右侧”区间。
对于[2,3],区间[3,4]具有最小的“右”起点;
对于[1,2],区间[2,3]具有最小的“右”起点。

示例 3:

输入: [ [1,4], [2,3], [3,4] ]
输出: [-1, 2, -1]

解释:对于区间[1,4]和[3,4],没有满足条件的“右侧”区间。
对于[2,3],区间[3,4]有最小的“右”起点。

5324ms
 1 /**
 2  * Definition for an interval.
 3  * public class Interval {
 4  *   public var start: Int
 5  *   public var end: Int
 6  *   public init(_ start: Int, _ end: Int) {
 7  *     self.start = start
 8  *     self.end = end
 9  *   }
10  * }
11  */
12 class Solution {
13     func findRightInterval(_ intervals: [Interval]) -> [Int] {
14         var res:[Int] = [Int]()
15         var v:[Int] = [Int]()
16         var m:[Int:Int] = [Int:Int]()
17         for i in 0..<intervals.count
18         {
19             m[intervals[i].start] = i
20             v.append(intervals[i].start)
21         }
22         v = v.sorted(by:>)
23         for a in intervals
24         {
25             var i:Int = 0
26             while(i < v.count)
27             {
28                 if v[i] < a.end
29                 {
30                     break
31                 }
32                 i += 1                
33             }
34             res.append((i > 0) ? m[v[i - 1]]! : -1)
35         }
36         return res
37     }
38 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap