Leetcode - Non-overlapping Intervals

Question

Given an array of intervals intervals where intervals[i] = [starti, endi], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Note that intervals which only touch at a point are non-overlapping. For example, [1, 2] and [2, 3] are non-overlapping.

This is an intervals question.

Idea

• Sort by starting point
• Keep a result variable
• Iterate through the intervals in sorted order and compare adjacent pairs
• Keep track of the previous end value where prev_env is the end value of the last interval in the non-overlapping case, and is the minimum of the current end value and the prev_end in the overlapping case.
  • The overlapping case is if the current intervals start value comes before prev_end
• This means, we get rid of the interval that has an end value that ends first

Solution