贪心算法

Input: [1,2,3], [1,1]
Output: 1
Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3. 
And even though you have 2 cookies, since their size is both 1, you could only make the child whose greed factor is 1 content.
You need to output 1.
Input: [1,2], [1,2,3]
Output: 2
Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2. 
You have 3 cookies and their sizes are big enough to gratify all of the children, 
You need to output 2.

 class  {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        
        int gi = g.length-1;
        int si = s.length-1;
        int res = 0;
        
        while(gi >= 0 && si >= 0){
            if(g[gi] <= s[si]){
                ++res;
                --gi;
                --si;
            }
            else{
                --gi;
            }
        }
        
        return res;
    }
}

s = "abc", t = "ahbgdc"
Return true.
s = "axc", t = "ahbgdc"
Return false.

class  {
    public boolean isSubsequence(String s, String t) { 
        int sLen = s.length();
        int tLen = t.length();
        
        if(sLen > tLen){
            return false;
        }
        
        int si = 0;
        int ti = 0;
        while(si < s.length() && ti < t.length()){
            if(s.charAt(si) == t.charAt(ti)){
                ++si;
                ++ti;
            }
            else{
                ++ti;
            }
        }
        
        return si == sLen;
    }
}

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.
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.
Input: [ [1,2], [2,3] ]
Output: 0
Explanation: You don't need to remove any of the intervals since they're already non-overlapping.

 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
class  {
    
    class MyComparator implements Comparator<Interval>{
        
        public int compare(Interval o1, Interval o2){
            if(o1.end != o2.end){
                return o1.end - o2.end;
            }
            else{
                return o1.start - o2.start;
            }
        }
    }
    
    public int eraseOverlapIntervals(Interval[] intervals) {
        
        if(intervals.length == 0){
            return 0;
        }
        
        Arrays.sort(intervals, new MyComparator());
        
        int cnt = 1;
        int pre = 0;
        for(int i = 1; i < intervals.length; ++i){
            if(intervals[i].start >= intervals[pre].end){
                ++cnt;
                pre = i;
            }
            
        }
        
        return intervals.length - cnt;
    }
}