# 19.07.2023 [435. Non-overlapping Intervals]

Minimum intervals to erase overlap

19.07.2023

435. Non-overlapping Intervals medium
blog post

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