LeetCode 435 - Non-overlapping Intervals


http://bookshadow.com/weblog/2016/10/30/leetcode-non-overlapping-intervals/
Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.
Note:
  1. You may assume the interval's end point is always bigger than its start point.
  2. Intervals like [1,2] and [2,3] have borders "touching" but they don't overlap each other.
Example 1:
Input: [ [1,2], [2,3], [3,4], [1,3] ]

Output: 1

Explanation: [1,3] can be removed and the rest of intervals are non-overlapping.
Example 2:
Input: [ [1,2], [1,2], [1,2] ]

Output: 2

Explanation: You need to remove two [1,2] to make the rest of intervals non-overlapping.
Example 3:
Input: [ [1,2], [2,3] ]

Output: 0

Explanation: You don't need to remove any of the intervals since they're already non-overlapping.
https://zhuanlan.zhihu.com/p/26657786
简单的逻辑就是,当有两个interval相互重叠的时候,我们一定要删去一个。那么删去哪一个呢?答案是删去end比较大的那个。这个可以用prove by contradiction轻松证明
http://www.cnblogs.com/grandyang/p/6017505.html
这道题给了我们一堆区间,让我们求需要至少移除多少个区间才能使剩下的区间没有重叠,那么我们首先要给区间排序,根据每个区间的start来做升序排序,然后我们开始要查找重叠区间,判断方法是看如果前一个区间的end大于后一个区间的start,那么一定是重复区间,此时我们结果res自增1,我们需要删除一个,那么此时我们究竟该删哪一个呢,为了保证我们总体去掉的区间数最小,我们去掉那个end值较大的区间,而在代码中,我们并没有真正的删掉某一个区间,而是用一个变量last指向上一个需要比较的区间,我们将last指向end值较小的那个区间;如果两个区间没有重叠,那么此时last指向当前区间,继续进行下一次遍历
    int eraseOverlapIntervals(vector<Interval>& intervals) {
        int res = 0, n = intervals.size(), last = 0;
        sort(intervals.begin(), intervals.end(), [](Interval& a, Interval& b){return a.start < b.start;});
        for (int i = 1; i < n; ++i) {
            if (intervals[i].start < intervals[last].end) {
                ++res;
                if (intervals[i].end < intervals[last].end) last = i;
            } else {
                last = i;
            }
        }
        return res;
    }
https://leetcode.com/problems/non-overlapping-intervals/discuss/91713/Java%3A-Least-is-Most
Actually, the problem is the same as "Given a collection of intervals, find the maximum number of intervals that are non-overlapping." (the classic Greedy problem: Interval Scheduling). With the solution to that problem, guess how do we get the minimum number of intervals to remove? : )
Sorting Interval.end in ascending order is O(nlogn), then traverse intervals array to get the maximum number of non-overlapping intervals is O(n). Total is O(nlogn).
Actually, the problem is the same as "Given a collection of intervals, find the maximum number of intervals that are non-overlapping." (the classic Greedy problem: Interval Scheduling). With the solution to that problem, guess how do we get the minimum number of intervals to remove? : )
X. Sort by end
为了知道有哪些是重叠的,我们先给所有的间隔排个序,这样就可以一个一个地看是否有重叠,间隔排序不像数字排序那么直接,需要自己进行定义,到底是比end的大小还是比start的大小呢?我们选择比end,如果比start,有可能一个start更小但范围很大的间隔,却包含了后面好几个start更大但是范围很小的间隔,而比end就没有这个问题,end基本就限制了你的范围。

那么比较end如果相同,还需要判断start吗?其实不需要了,对于同一个end值的两个间隔,无论我们留哪一个(只要能留,也就是说只要范围没重叠),另一个都一定会被抛弃,且对后续的间隔没有任何影响。

排序我们就可以遍历间隔数组,比较后一个间隔的start是否大于前一个的end,大于则无重叠,我们就留下来,否则就抛弃掉。最后得出抛弃掉的数量就可以

Do you know why sort by end time instead of by start time?
[ [1,4], [2,3], [3,4] ], the interval with early start might be very long and incompatible with many intervals. But if we choose the interval that ends early, we'll have more space left to accommodate more intervals.
  1. Sort Intervals by end.
  2. Count valid intervals (non-overlapping).
  3. Answer is len - count
    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 = 0; 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;
        }
    }
http://blog.csdn.net/mebiuw/article/details/53054380
1、按照起始位置排序 
2、按照顺序,两个指针遍历,一前一后,如果当前位置和上一个位置不冲突就顺序平移两个指针(后指针的值给前指针,然后后指针移动到下一位),如果冲突的话,那么前指针则变成当前两个指针当中覆盖最小的一个(贪心所在),后指针移动到下一个位置就好
public int eraseOverlapIntervals(Interval[] intervals) { // 按照起始位置进行排序 Arrays.sort(intervals,(x,y)->(x.start)-(y.start)); int count=0,j=0; // 贪心法,如果上一个位置j和当前位置i冲突了,那么进行判断,
如果当前位置的末尾小于上一个边界的末尾,那么删除上一个位置
(因为覆盖的更少,每步选择最有可能不造成重复的),反之如果当前位置尾部覆盖的更多,
那么就删除i的位置。删除的方式通过控制j的取值进行 for(int i=1;i<intervals.length;i++) { if(intervals[j].end>intervals[i].start){ j=intervals[i].end<intervals[j].end?i:j; count++; }else //没有重复 j=i; } return count; }

https://discuss.leetcode.com/topic/65828/java-solution-with-clear-explain
First we sort the array by below rules
  • 1) sort by end, smaller end in front
  • 2) if end is same, sort by start, bigger start in front
Then, visited array by end. If we visited next closest end interval, access the bigger start priority.
when end is same, the bigger start one has greater possibility of convergence. So we can put those front. Actually, we only sort by end is ok, like below
Arrays.sort(intervals, new Comparator<Interval>() {
    @Override
    public int compare(Interval o1, Interval o2) {
        return o1.end - o2.end;  //only sort by end
    }
});
public int eraseOverlapIntervals(Interval[] intervals) {
        Arrays.sort(intervals, new Comparator<Interval>() {
            @Override
            public int compare(Interval o1, Interval o2) {
                if (o1.end != o2.end) return o1.end - o2.end;  //first sort by end
                return o2.start - o1.start;  //second sort by start
            }
        });

        int end = Integer.MIN_VALUE;
        int count = 0;
        for (Interval interval : intervals) {
            if (interval.start >= end) end = interval.end;
            else count++;
        }

        return count;
    }
贪心算法(Greedy Algorithm)
优先按照终点,然后按照起点从小到大排序
利用变量end记录当前的区间终点,end初始化为负无穷
遍历排序后的区间,若当前区间的起点≥end,则更新end为当前区间的终点,并将计数器ans+1
ans为可以两两互不相交的最大区间数,len(intervals) - ans即为答案
def eraseOverlapIntervals(self, intervals): """ :type intervals: List[Interval] :rtype: int """ invs = sorted((x.end, x.start) for x in intervals) end = -0x7FFFFFFF ans = 0 for e, s in invs: if s >= end: end = e ans += 1 return len(intervals) - ans
X. Sort by start
https://blog.csdn.net/fuxuemingzhu/article/details/82728387
看到区间最值题一般想到排序+贪心。这个题和452. Minimum Number of Arrows to Burst Balloons挺相似。

这个题的做法也不难,这么思考:我们尽量移除那些覆盖最广的区间。

先对所有区间的起点进行排序,然后进行遍历,如果新的区间起点比老的区间终点小的话,说明有重叠,需要移除区间,移除哪个区间呢?当然是终点最靠后的终点。

我们使用last指针指向上个保留下来的节点,如果intervals[i].end < intervals[last].end,则代表新的区间终点更靠前,所以使用第i个节点代表last,也就是说移除了上面的那个last。然后统计移除了多少次区间即可。

https://zhuhan0.blogspot.com/2017/03/leetcode-non-overlapping-intervals.html
The idea is to sort the array based on the intervals start points and use a greedy approach.

After the array is sorted, iterate through the array and use a local variable "end" to keep track of the smallest end point of current overlapping intervals. The reason is that we want to delete all overlapping intervals except the one that has the smallest end point, so that the next interval won't overlap with it.

Once we iterate through a group of overlapping intervals, we update "end" to be the end point of the next interval.
    public int eraseOverlapIntervals(Interval[] intervals) {
        if (intervals.length < 2) {
            return 0;
        }
        
        Arrays.sort(intervals, new Comparator<Interval>(){
            public int compare(Interval i1, Interval i2) {
                return i1.start - i2.start;
            }
        });
        
        int end = intervals[0].end;
        int min = 0;
        
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i].start < end) {
                end = Math.min(end, intervals[i].end);
                min++;
            } else {
                end = intervals[i].end;
            }
        }
        
        return min;
    }
https://discuss.leetcode.com/topic/66200/simple-solution
  1. Order intervals by start point.
  2. Record the end of the last valid interval.
  3. For each interval, if is start point is >= the end of the last valid interval, increment the count of valid intervals, and move the end point to the end of the current interval. Otherwise just set the new end point to the minimum between the two overlapping intervals.
  4. Return the difference between the number of intervals in the input array and the number of valid intervals you found in the previous way.
public int eraseOverlapIntervals(Interval[] intervals) {
 if(intervals==null || intervals.length==0) return 0;
 Arrays.sort(intervals, new Comparator<Interval>() {
  public int compare(Interval i1, Interval i2) {
   return i1.start-i2.start;
  }
 });
 int count=1;
 int lastEnd = intervals[0].end;
 for(int i=1;i<intervals.length;i++) {
  Interval currentInterval = intervals[i];
  if(currentInterval.start>=lastEnd) {
   count++;
   lastEnd=currentInterval.end;
  } else {
   lastEnd=Math.min(currentInterval.end,lastEnd);
  }
 }
 return intervals.length-count;
}

https://hintpine.wordpress.com/2016/10/31/leetcode-non-overlapping-intervals/
First, let’s define solution to be a group who has maximum non-overlapping intervals, and the intervals are sorted by end values. There might be multiple solutions to the input. For example, if the input is [[1,2], [1,3], [5,6]], there are two solutions, [[1,2], [5,6]] and [[1,3], [5,6]].
Now, sort the intervals by end values. Then, we can say the first interval must belong to some solution.
Proof:
Suppose the first interval, name it A, does not belong to any solution. Then, use B to denote the first interval of solution. It must be either one of following cases:
  1. B is non-overlapping with A. In this case, A can be safely inserted before B to form a new solution.
  2. B is overlapping with A. Because all other intervals of the solution don’t overlap with B, we can safely replace B with A to form a new solution.
So, both cases contradict the assumption. Thus, A must belong to some solution. Q.E.D.
Since A is fixed, in that solution all those intervals who overlap with A definitely don’t belong to the solution. So, we can safely remove those intervals until an interval whose start value is greater than or equal to A’s end value. Then, as proven, we can add that interval into the solution.
Repeat the above way, we can generate a solution, and the count of those removed intervals is the final return value.

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts