712431. Non-overlapping Intervals
Non-overlapping Intervals
Slug: non-overlapping-intervals
Difficulty: Medium
Id: 712431
Topic Tags: Arrays, Greedy, Sorting, Data Structures, Algorithms
Company Tags: None
Summary
Given a set of intervals, where each interval is represented by its start and end points, the problem requires you to find the maximum number of non-overlapping intervals that can be selected. This problem involves using greedy algorithms and sorting techniques.
Detailed Explanation
The algorithm for this problem involves sorting all the intervals based on their end points. Then, we iterate over the sorted intervals and select the one with the earliest end point. We continue selecting intervals until we have used up all the intervals or no more non-overlapping intervals can be selected.
Here's a step-by-step breakdown of the solution:
- Sort the intervals based on their end points.
- Initialize a variable
countto keep track of the number of non-overlapping intervals selected so far. - Iterate over the sorted intervals and for each interval, check if it doesn't overlap with the previously selected interval (i.e., its start point is greater than or equal to the end point of the previously selected interval).
- If the current interval does not overlap, select it and increment
count. - Return
countas the maximum number of non-overlapping intervals that can be selected.
Time complexity analysis: The time complexity of this algorithm is O(n log n) due to the sorting step, where n is the number of intervals.
Space complexity analysis:
The space complexity of this algorithm is O(1), since we only use a constant amount of space to store variables like count and the current interval.
Here's an ASCII art diagram illustrating the process:
Interval 1: [1,3]
Interval 2: [2,4]
Interval 3: [5,7]
Sorted intervals:
[1,3]
[2,4]
[5,7]
Selected intervals:
[1,3]
[5,7]
Count: 2
Optimized Solutions
Java
import java.util.Arrays;
public class NonOverlappingIntervals {
public static int maxNonOverlapping(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> Integer.compare(b[1], a[1]));
int count = 0;
int prevEnd = -1;
for (int[] interval : intervals) {
if (interval[0] >= prevEnd) {
count++;
prevEnd = interval[1];
}
}
return count;
}
}