interval scheduling maximization problem
greedy solution
rank the intervals by finishing time
initialize ending time as -inf
if the start time if the interval intersect the last interval's end time , then remove this interval.
reason: after sorting the intervals by their ending time, the intervals that all intersect the ending time of interval x all intersect each other. there will only be one interval in the group that will be in the optimal solution set, therefore, remove all intervals other than x.
# Definition for an interval.
# class Interval(object):
# def __init__(self, s=0, e=0):
# self.start = s
# self.end = e
class Solution(object):
def eraseOverlapIntervals(self, intervals):
"""
:type intervals: List[Interval]
:rtype: int
"""
res=0
end=float('-inf')
intervals.sort(key=lambda x:x.end)
for item in intervals:
if item.start>=end:
end=item.end
else:
res+=1
return res
435. Non-overlapping Intervals
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 题目如下： Given a collection of intervals, find the minimum n...
- Le silence est généralement définie comme l'absence de so...
- Richard Liu最近在央视《对话》节目上称,“财报显示按照美国会计准则京东去年亏损94亿元,但真正亏损额为8...
- Android编译针对方法数量有一个64K的限制，理论上是65535，在Android Studio编译打包的过程...
