帮我写一个简单的贪心算法代码
时间: 2024-05-03 15:22:55 浏览: 62
贪心算法 code
以下是一个简单的贪心算法代码,用于寻找能够覆盖所有点的最小数量的区间:
```
def greedy_intervals(intervals):
intervals.sort(key=lambda x: x[1]) # 按照右端点从小到大排序
covered = set()
selected = []
for interval in intervals:
if interval[0] <= min(covered): # 如果当前区间左端点在已覆盖的区间内,则跳过
continue
covered.update(range(interval[0], interval[1]+1)) # 更新已覆盖的区间
selected.append(interval) # 将当前区间加入选中的列表中
return selected
```
这个算法的时间复杂度为 $O(n\log n)$,其中 $n$ 是区间的数量,因为需要对区间进行排序。
阅读全文