Assign Cookies

edyluisrey · edyluisrey · commit 975eeb748c18 · 2018-02-11T19:22:32.000-05:00
diff --git a/src/leetcode2018/AssignCookies.java b/src/leetcode2018/AssignCookies.java
@@ -1,28 +1,51 @@
 package leetcode2018;
 
-import java.util.Arrays;
-
 public class AssignCookies {
 	public int findContentChildren(int[] g, int[] s) {
-		Arrays.sort(g);
-        Arrays.sort(s);
-		int t = 0;
-		for(int i = 0; i< g.length; i++){
-		    if(isContent(g[i], s))
-		        t++;
+		if(g.length == 0 || s.length == 0) return 0;
+		mergeSort(g, 0, g.length-1);
+		mergeSort(s, 0, s.length-1);
+		int i = 0;
+		for(int j = 0; i< g.length && j< s.length; j++){
+		    if(g[i] <= s[j])
+		       i++;
+		}
+		return i;
+    }
+    
+    public void mergeSort(int[] nums, int l, int p){
+		if(l==p){
+		    return;
 		}
-		return t;
+		int mid = (l+p)/2;
+		mergeSort(nums, l, mid);
+		mergeSort(nums, mid+1, p);
+		merge(nums, l, mid+1, p);
     }
     
-    public boolean isContent(int n, int[] s){
-		for(int i = 0; i< s.length; i++){
-		    if(s[i]!=-1){
-		        if(s[i] >= n){
-		            s[i]=-1;
-		            return true;
-		        }
-		    }
+    public void merge(int[] nums, int left, int mid, int rightEnd){
+		int right = mid;  
+		int k=0;
+		int n= rightEnd-left+1;
+		int lower =left;
+		int[] temp= new int[n]; 
+		while(left<=mid-1 &&  right<= rightEnd){
+			if(nums[left]<=nums[right]){
+				temp[k++]= nums[left++];
+			}else{
+				temp[k++]= nums[right++];
+			}
+		} 
+		while(left<=mid-1){
+			temp[k++]= nums[left++];
+		}
+		while(right<=rightEnd){
+			temp[k++]= nums[right++];
+		}
+		
+		for(int i=0; i<n;i++){
+			nums[lower+i] = temp[i];
 		}
-		return false;
+    	
     }
 }
