LeetCode 435 Non-overlapping Intervals - Why Naive Fails

The trap

Try all subsets of intervals, check which are non-overlapping, find the largest subset.

With nn intervals, 2n2^n subsets to check. Exponential time.

Can you greedily decide which intervals to keep?