LeetCode 435 Non-overlapping Intervals - Example and Complexity Analysis

Trace intervals = [[1,2],[2,3],[3,4],[1,3]].

Sort by end time: [[1,2],[2,3],[1,3],[3,4]].

lastEnd = -infinity, removed = 0.

[1,2]: start=1 >= lastEnd. Keep. lastEnd = 2. [2,3]: start=2 >= 2. Keep. lastEnd = 3. [1,3]: start=1 < 3. Overlaps! Remove. removed = 1. [3,4]: start=3 >= 3. Keep. lastEnd = 4.

Kept: 3 intervals. Removed: $1$.

$O(n \log n)$ time for sorting. $O(1)$ extra space (or $O(n)$ for sort).