Non-overlapping Intervals

Try to solve the Non-overlapping Intervals problem.

Statement

Given an array of intervals where intervals[i] contains the half-open intervalAn interval that contains only one of its boundary elements. The “(” parenthesis denotes the exclusion of the starting point. The “]” bracket denotes the inclusion of the ending point., (starti,endi](start_{i}​, end_{i}], your task is to find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Note: Two intervals (a,b](a, b] and (c,d](c, d] are considered overlapping if there exists a value xx such that a<xba < x \leq b and c<xdc < x \leq d. In other words, if there is any point within both intervals (excluding their starting points) where both intervals have values, they are considered overlapping. For example, the intervals (7,11](7, 11] and (10,12](10, 12] are overlapping, whereas the intervals (2,4](2, 4] and (4,5](4, 5] are non-overlapping.

Constraints:

  • 11 \leqintervals.length 103\leq 10^3

  • intervals[i].length ==2== 2

  • 5×104starti<endi5×104−5 \times 10^4 \leq start_{i} < end_{i} \leq 5 \times 10^4

Examples

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.