Given a collection of intervals, find the maximum number of non-overlapping intervals you can select.
Example 1:
Input: [[1,2],[2,3],[3,4],[1,3]] Output: 3 Explanation: [1,2], [2, 3] and [3, 4] are non-overlapping.
Note:
- You may assume the interval's end point is always bigger than its start point.
- Intervals like [1,2] and [2,3] have borders "touching" but they don't overlap each other.
Your algorithm should run in O(n log n) time. Apart from the sorting, the greedy pass needs only O(1) extra space.
Walkthroughs of the solution. Try the steps first, then watch to compare approaches.
Solution #1 · O(n log n)
Free plan: 30 tutor messages. Premium is unlimited.
Saved
Ctrl + Enter to check
