Java Greedy with Explanation


  • 0
    W
    1. sort with start
      2.compare the pre and current interval. current come from 1 to end
      if( pre.end < cur.start) count++ and pre = cur, compare the pre and cur again
      else {
      choose the pre or the cur as a pre. there are two situations
      a. if pre contains the cur, choose cur as a pre
      b.if pre and cur just have an interaction, choose the pre again
      }
      //a, b情况是贪心算法的关键,可以这么理解:A如果pre完全包含了cur,说明我选cur可以有更多的连接串,否则选pre有更多的连接串。
        public int findLongestChain(int[][] pairs) {
            Arrays.sort(pairs, (a,b) -> a[0] - b[0]);
            int count = 1;
            int[] pre = pairs[0];
            for(int i = 1; i < pairs.length; i++) {
                int[] cur = pairs[i];
                if(pre[1] >= cur[0]) { // inter section
                    if(pre[1] >= cur[1]) {
                        pre = cur;
                    }
                } else {
                    count++;
                    pre = cur;
                }
            }
            return count;
        }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.