package
0.0.0-20241220224003-b7cf03a90b2b
Repository: https://github.com/szhou12/leetcode-go.git
Documentation: pkg.go.dev
# README
435. Non-overlapping Intervals
Solution idea
Greedy Algorithm
-
难点：应该sort by start time? 还是 sort by end time?
- Sort by end time: 就要从左向右遍历，因为右边界越小越好，只要右边界越小，留给下一个区间的空间就越大，所以从左向右遍历，优先选右边界小的。
- Sort by start time: 就要从右向左遍历，因为左边界数值越大越好（越靠右），这样就给前一个区间的空间就越大，所以可以从右向左遍历。
Time complexity = $O(n\log n)$
正确性证明：参考MPCS - Algorithm课讲义