LeetCode Entry

435. Non-overlapping Intervals

19.07.2023 medium 2023 kotlin

Minimum intervals to erase overlap

435. Non-overlapping Intervals medium blog post substack image.png

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/280

Problem TLDR

Minimum intervals to erase overlap

Intuition

First idea, is to sort the array by from. Next, we can greedily take intervals and remove overlapping ones. But, to remove the minimum number, we can start with removing the most long intervals.

Approach

  • walk the sweep line, counting how many intervals are non overlapping
  • only move the right border when there is a new non overlapping interval
  • minimize the border when it shrinks

Complexity

  • Time complexity: \(O(nlog(n))\)

  • Space complexity: \(O(1)\)

Code


    fun eraseOverlapIntervals(intervals: Array<IntArray>): Int {
        intervals.sortWith(compareBy({ it[0] }))
        var border = Int.MIN_VALUE
        return intervals.count { (from, to) ->
          (border > from).also {
            if (border <= from || border > to) border = to
          }
        }
    }