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 and use 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