Non-overlapping Intervals — Medium Coding Interview Question

Return the minimum number of intervals you need to remove to make the rest non-overlapping.

Example

Input: intervals = [[1,2],[2,3],[3,4],[1,3]]

Output: 1

Constraints

• 1 <= intervals.length <= 10^5

Topics & Companies

Topics: greedy, sorting

Asked by: Meta, Amazon

Optimal Solution Complexity

Time complexity: O(n log n). Space complexity: O(1).

Practice more

• All DSA Problems
• DSA Patterns