Non-overlapping Intervals – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
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.
Example 1:
Input: intervals = [[1,2],[2,3],[3,4],[1,3]] Output: 1 Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping.
Example 2:
Input: intervals = [[1,2],[1,2],[1,2]] Output: 2 Explanation: You need to remove two [1,2] to make the rest of the intervals non-overlapping.
Example 3:
Input: intervals = [[1,2],[2,3]] Output: 0 Explanation: You don't need to remove any of the intervals since they're already non-overlapping.
Constraints:
1 <= intervals.length <= 105
intervals[i].length == 2
-5 * 104 <= starti < endi <= 5 * 104
C++ Non-overlapping Intervals LeetCode Solution
bool comp(vector<int> &a,vector<int> &b) {
return a[1]<b[1];
}
class Solution {
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
int ans=-1;
if(intervals.size()==0) return 0;
sort(intervals.begin(),intervals.end(),comp); //custom comperator is used.
vector<int> prev= intervals[0];
for(vector<int> i: intervals) {
if(prev[1]>i[0]) {
ans++; //we dont update previous, because i[1] will be grater then prev[1]
}else prev=i; // we want the end point to be minimum
}
return ans; //ans was initially made -1 because our prev and intervals[0] will always match
}
};
Java Non-overlapping Intervals LeetCode Solution
public int eraseOverlapIntervals(Interval[] intervals) {
if (intervals.length == 0) return 0;
Arrays.sort(intervals, new myComparator());
int end = intervals[0].end;
int count = 1;
for (int i = 1; i < intervals.length; i++) {
if (intervals[i].start >= end) {
end = intervals[i].end;
count++;
}
}
return intervals.length - count;
}
class myComparator implements Comparator<Interval> {
public int compare(Interval a, Interval b) {
return a.end - b.end;
}
}
Python 3 Non-overlapping Intervals LeetCode Solution
def eraseOverlapIntervals(intervals):
end, cnt = float('-inf'), 0
for s, e in sorted(intervals, key=lambda x: x[1]):
if s >= end:
end = e
else:
cnt += 1
return cnt
Array-1180
String-562
Hash Table-412
Dynamic Programming-390
Math-368
Sorting-264
Greedy-257
Depth-First Search-256
Database-215
Breadth-First Search-200
Tree-195
Binary Search-191
Matrix-176
Binary Tree-160
Two Pointers-151
Bit Manipulation-140
Stack-133
Heap (Priority Queue)-117
Design-116
Graph-108
Simulation-103
Prefix Sum-96
Backtracking-92
Counting-86
Sliding Window-73
Linked List-69
Union Find-66
Ordered Set-48
Monotonic Stack-47
Recursion-43
Trie-41
Binary Search Tree-40
Divide and Conquer-40
Enumeration-39
Bitmask-37
Queue-33
Memoization-32
Topological Sort-31
Geometry-30
Segment Tree-27
Game Theory-24
Hash Function-24
Binary Indexed Tree-21
Interactive-18
Data Stream-17
String Matching-17
Rolling Hash-17
Shortest Path-16
Number Theory-16
Combinatorics-15
Randomized-12
Monotonic Queue-9
Iterator-9
Merge Sort-9
Concurrency-9
Doubly-Linked List-8
Brainteaser-8
Probability and Statistics-7
Quickselect-7
Bucket Sort-6
Suffix Array-6
Minimum Spanning Tree-5
Counting Sort-5
Shell-4
Line Sweep-4
Reservoir Sampling-4
Eulerian Circuit-3
Radix Sort-3
Strongly Connected Componen-t2
Rejection Sampling-2
Biconnected Component-1