由右至左对速度进行合并,转化为单调增序列
时间复杂度 $O(n)$
Python 代码
N = int(input())
l = []
for i in range(N):
_,v = map(int,input().split())
l.append(v)
ans = 1
for i in range(len(l)-2,-1,-1):
if l[i]>l[i+1]:
l[i] = l[i+1]
else:
ans += 1
print(ans)