LeetCode Entry

646. Maximum Length of Pair Chain

26.08.2023 medium 2023 kotlin

Max count non-overlaping intervals

646. Maximum Length of Pair Chain medium blog post substack image.png

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 sorting

  • Space 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 }
      }
    }