Given a collection of intervals,find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapPing.
Note:
You may assume the interval‘s end point is always bigger than its start point. Intervals like [1,2] and [2,3] have borders "touching" but they don‘t overlap each other.Example 1:
input: [ [1,2],[2,3],[3,4],[1,3] ]Output: 1Explanation: [1,3] can be removed and the rest of intervals are non-overlapPing.
Example 2:
input: [ [1,2] ]Output: 2Explanation: You need to remove two [1,2] to make the rest of intervals non-overlapPing.
Example 3:
input: [ [1,3] ]Output: 0Explanation: You don‘t need to remove any of the intervals since they‘re already non-overlapPing.
给定一个区间的集合,找到需要移除区间的最小数量,使剩余区间互不重叠。
注意:
可以认为区间的终点总是大于它的起点。 区间 [1,2] 和 [2,3] 的边界相互“接触”,但没有相互重叠。示例 1:
输入: [ [1,3] ]输出: 1解释: 移除 [1,3] 后,剩下的区间没有重叠。
示例 2:
输入: [ [1,2] ]输出: 2解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
示例 3:
输入: [ [1,3] ]输出: 0解释: 你不需要移除任何区间,因为它们已经是无重叠的了。
76ms
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 eraSEOverlAPIntervals(_ intervals: [Interval]) -> Int {14 var intervals = intervals15 if intervals.isEmpty {return 0}16 intervals.sort(by:{(_ a:Interval,_ b:Interval) -> Bool in return a.start < b.start})17 var res:Int = 018 var n:Int = intervals.count19 var endLast:Int = intervals[0].end20 for i in 1..<n21 {22 var t:Int = endLast > intervals[i].start ? 1 : 023 endLast = t == 1 ? min(endLast,intervals[i].end) : intervals[i].end24 res += t 25 }26 return res27 }28 }
80ms
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 eraSEOverlAPIntervals(_ intervals: [Interval]) -> Int {14 if intervals.count <= 1 {15 return 016 }17 18 var move = 119 var ts = intervals20 ts.sort { (i1,i2) -> Bool in21 return i1.end <= i2.end 22 }23 24 var temp = ts[0]25 for i in 1..<ts.count {26 let start = ts[i].start27 if start >= temp.end {28 move += 129 temp = ts[i]30 }31 }32 return intervals.count - move33 }34 }总结
以上是内存溢出为你收集整理的[Swift]LeetCode435. 无重叠区间 | Non-overlapping Intervals全部内容,希望文章能够帮你解决[Swift]LeetCode435. 无重叠区间 | Non-overlapping Intervals所遇到的程序开发问题。
如果觉得内存溢出网站内容还不错,欢迎将内存溢出网站推荐给程序员好友。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)