不需要暴力遍历每一个点,只检测起点和重点的位置
有些题目和线段树结合
lintcode-391 · 数飞机
# 本题也可以使用前缀和 class Solution: def countOfAirplanes(self, airplanes): room=[] for i in airplanes: room.append((i.start, 1)) room.append((i.end, -1)) tmp = 0 ans = 0 room = sorted(room) for idx, cost in room: tmp += cost ans = max(ans,tmp) return ans
时间复杂度:O(nlog(n)) 空间复杂度:O(time)
一文读懂扫描线算法 - 小水的文章 - 知乎
Last updated 5 months ago