Find min merge intervals - Facebook


https://www.1point3acres.com/bbs/thread-224128-1-1.html给定一堆interval(如果我们管这个list叫IntervalList), 和一个target interval
我们的目标是去merge这些interval,让merge的结果能够『cover』这个target interval, 求这种merge所需的原interval的最少个数是多少

有点抽象,举个栗子
IntervalList: [-1, 9]  [ 1, 10] [ 0, 3] [ 9, 10] [ 3, 14] [ 2, 9] [10, 16]
target interval: [ 2, 15]
在这个栗子中,我们发现要想cover[2,15]有好几种方法,比如:
[-1, 9]   + [ 9, 10] + [10, 16] 或者  [ 1, 10] + [10, 16]-baidu 1point3acres
我们要的是merge个数最少的方法,所以这里应该返回2
https://lina.bitcron.com/post/code/2018-summer-fb-intern-mian-jing
 public int minCover( List<Interval> list, Interval target){
    Map<Integer,Integer> map = new HashMap<Integer,Integer>();
    Collections.sort(list, new Comparator<Interval>(){
        public int compare(Interval a,Interval b){
        if(a.start-b.start==0) return a.end-b.end;
        return a.start-b.start;
        }
    });
    int res = 0;
    for(Interval i :list){
        if(i.end>=target.start&&i.start<=target.start){
            map.put(i.end,1);
        }
        else if(i.start>target.start){
            int min = Integer.MAX_VALUE;
            for(int k = i.start;k<=Math.min(target.end,i.end));k++){
                if(map.containsKey(k)) min = Math.min(min,map.get(k));
            }
            if(min!=Integer.MAX_VALUE)  map.put(i.end,min+1);
        }
        if(map.containsKey(i.end)&&i.end>=target.end)res = Math.min(res,map.get(i.end));
    }
    return res;
 }
感觉第二轮的题更像是greedy。先把所有intervals按start排序,然后遍历。首先我们要从那些start小于等于target.start的intervals中选end最大的那个,假设我们用A来表示那个选出来的interval。如果A.end小于target.end,我们就得继续遍历,从那些start小于等于A.end的intervals中选end最大的那个。最终返回所选的interval个数。时间复杂度是O(nlogn)。隐约觉得很像jump game II。

层主考虑下特殊情况,所有区间都比target区间大,这样的话层主的第一个loop是跳不出来的
有道理!不过这样就没有答案了诶。那就在loop前加一行判断好了!
  1.         public int find(Interval[] intervals, Interval target){
  2.                 if(intervals == null || intervals.length == 0) return -1;
  3.                 Arrays.sort(intervals, new Comparator<Interval>(){
  4.                         public int compare(Interval a, Interval b){
  5.                                 return a.start - b.start;
  6.                         }
  7.                 });
  8.                 int res = 0;
  9.                 int i = 0;
  10.                 int start = target.start;
  11.                 while(i < intervals.length){
  12.                         int cur = greedy(intervals, i, start);
  13.                         res++;
  14.                         if(intervals[cur].end >= target.end) return res;
  15.                         i = cur;
  16.                         start = intervals[cur].end;
  17.                 }
  18.                 return -1;
  19.         }

  20.         public int greedy(Interval[] intervals, int i, int tar){
  21.                 int res = i;
  22.                 while(i < intervals.length){
  23.                         if(intervals[i].start <= tar && intervals[i].end > intervals[res].end){
  24.                                 res = i;
  25.                         }else if(intervals[i].start > tar) return res;
  26.                         i++;
  27.                 }
  28.                 return res;
  29.         }
https://zhuanlan.zhihu.com/p/26657786
这里有两点说明。第一,其实并不需要全部排序,只需要找出和target有overlap的interval进行排序。第二,关于greedy。在inner while loop里面,我们所需要找的,就是满足start比cur_target要小的interval中,end最大的那个。这样去最大的end可以让加入的这个interval,最有价值,延展到最远。一开始的cur_target是target的start,后面的cur_target就是上一个加入的interval的end(为了保持区间不中断)。
def find_min_intervals(intervals, target): 
 intervals.sort() 
 res = 0 
 cur_target = target[0] 
 i = 0 
 max_step = 0 
 while i < len(intervals) and cur_target < target[1]: 
  while i < len(intervals) and intervals[i][0] <= cur_target: 
   max_step = max(max_step, intervals[i][1]) 
   i += 1 
  cur_target = max_step 
  res += 1 
 return res if cur_target >= target[1] else 0

第二轮我的思路是用DP做
先将IntervalList按找start排序O(nlgn)
再设立Dp方程
DP代表了对于第i个interval[curStart, curEnd],想要达到[targetStart, curEnd]所需要merge的个数

补充内容 (2017-1-25 12:20):
转换方程就是对于dp,我们去遍历之前所有的dp状态,尝试去与之前的interval去和当前的inreval进行一次merge,如果能merge,dp就可能可以更新为dp[j] + 1

补充内容 (2017-1-25 12:24):
最终再遍历一次dp,看下curEnd是否大于targetEnd,如果是的话,就可以去更新最终的答案了
(直接也应该对达不到targetStart的interval进行特殊处理)
这样最终的复杂度是O(n^2)




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