Intervals
Non-Overlapping Intervals
DESCRIPTION (inspired by Leetcode.com)
Write a function to return the minimum number of intervals that must be removed from a given array intervals, where intervals[i] consists of a starting point starti and an ending point endi, to ensure that the remaining intervals do not overlap. Intervals that only touch at their endpoints are not considered overlapping (e.g., [2,5] and [5,7] do not overlap).
Input:
intervals = [[1,3],[5,8],[4,10],[11,13]]
Output:
1
Explanation: Removing the interval [4,10] leaves all other intervals non-overlapping.
Explanation
def nonOverlappingIntervals(intervals):if not intervals:return 0intervals.sort(key=lambda x: x[1])end = intervals[0][1]count = 1for i in range(1, len(intervals)):# Non-overlapping interval foundif intervals[i][0] >= end:end = intervals[i][1]count += 1return len(intervals) - count
sort by end time
0 / 1
def nonOverlappingIntervals(intervals):if not intervals:return 0intervals.sort(key=lambda x: x[1])end = intervals[0][1]count = 1for i in range(1, len(intervals)):# Non-overlapping interval foundif intervals[i][0] >= end:end = intervals[i][1]count += 1return len(intervals) - count
i = 1
0 / 1
def nonOverlappingIntervals(intervals):if not intervals:return 0intervals.sort(key=lambda x: x[1])end = intervals[0][1]count = 1for i in range(1, len(intervals)):# Non-overlapping interval foundif intervals[i][0] >= end:end = intervals[i][1]count += 1return len(intervals) - count
i = 2
0 / 4
Solution
def nonOverlappingIntervals(intervals):if not intervals:return 0intervals.sort(key=lambda x: x[1])end = intervals[0][1]count = 1for i in range(1, len(intervals)):# Non-overlapping interval foundif intervals[i][0] >= end:end = intervals[i][1]count += 1return len(intervals) - count
non-overlapping intervals
0 / 8
Test Your Knowledge
Login to take the complexity quiz and track your progress
Complexity Analysis
Time Complexity: O(n log n) where n is the number of intervals. The time complexity is dominated by the sorting step.
Space Complexity: O(n) The sorting step requires O(n) auxiliary space in most language implementations (e.g., Timsort in Python, merge sort in Java). The greedy scan itself only uses two extra variables.