Greedy Java AC Solution


  • 0

    This question is almost the same as the activity selection in greedy problem chapter of CLRS.
    We just need to treat the 1st element which might be negative number to be the begin time.
    activity selection

    public int findLongestChain(int[][] pairs) {
            if(pairs==null||pairs.length==0) return 0;
            int n = pairs.length;
            Arrays.sort(pairs,new Comparator<int[]>(){
                public int compare(int [] o1,int [] o2){
                    return o1[1] - o2[1];
                }
            });
            int num = 1;
            int i = 1;
            int index = 0;
            while(i<n){
                if(pairs[i][0]>pairs[index][1]){
                    index = i;
                    num++;
                }
                i++;
            }
            return num;
        }
    

  • 0

    Neat! Sorting ends is a better idea.


Log in to reply
 

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