26.08.2023
646. Maximum Length of Pair Chain medium
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/320
Problem TLDR
Max count non-overlaping intervals
Intuition
The naive Dynamic Programming n^2 solution works, in a DFS choose between taking or skipping the pair, and cache by pos
and prev
.
Another solution, is just a line sweep algorithm: consider all ends
of the intervals in increasing order, skipping the overlapping ones. It will be optimal, as there are no overlapping intervals past the end
.
Approach
Sort and use the border
variable, that changes when from > border
.
Complexity
Time complexity:
O(nlog(n)), for sortingSpace complexity:
O(n), for the sorted array
Code
fun findLongestChain(pairs: Array<IntArray>): Int {
var border = Int.MIN_VALUE
return pairs.sortedWith(compareBy({ it[1] }))
.count { (from, to) ->
(from > border).also { if (it) border = to }
}
}