Greedy.txt

SOLUTIONS OF THESE QUESTIONS ARE EITHER ON GFG OR ON LEETCODE.
---------------------------------------Greedy-----------------------------------------

1. Job sequencing Problem
//Function to find the maximum profit and the number of jobs done.
    //Greedy Approach
    public int[] JobScheduling(Job arr[], int n)
    {
       Arrays.sort(arr,(a,b)->(b.profit-a.profit));
       
       int max_deadline=0;
       for(int i=0;i<n;i++){
           if(arr[i].deadline>max_deadline){
               max_deadline=arr[i].deadline;
           }
       }
       int[] result=new int[max_deadline+1];
       for(int i=1;i<=max_deadline;i++){
           result[i]=-1;
       }
       int count_jobs=0,job_profit=0;
       //traverse through (i==job_id);
       for(int i=0;i<n;i++){
           for(int j=arr[i].deadline;j>0;j--){
               if(result[j]==-1){
                 result[j]=i;   
                 count_jobs++;
                 job_profit+=arr[i].profit;
                 break;
               }
           }
       }
       int[]res=new int[2];
       res[0]=count_jobs;
       res[1]=job_profit;
       return res;
    }
---------------------------------------------------------------------------------
2. Chocolate Distribution Problem, Minimum Cost of ropes , Rearrange characters in a string such that no two adjacent are same -> These 3 questions are already done in some previous section of problems.
---------------------------------------------------------------------------------
3. N meetings in one room ->Also known as Activity Selection Problem
Intuition-> the earlier the meeting will end the more we call organize. that's why in this question we sorted the array accoding to the end time.
static class meeting {
		int start;
		int end;
		int pos;

		meeting(int s, int e, int p) {
			this.start = s;
			this.end = e;
			this.pos = p;
		}
	}

	static class meetingComparator implements Comparator<meeting> {
		@Override
		public int compare(meeting o1, meeting o2) {
			if (o1.end < o2.end)
				return -1;
			else if (o1.end > o2.end)
				return 1;
			else if (o1.pos < o2.pos)
				return -1;
			return 1;
		}
	}

	public static int maxMeetings(int[] start, int[] end, int n) {
		ArrayList<meeting> meet = new ArrayList<>();
		for (int i = 0; i < n; i++) {
			meet.add(new meeting(start[i], end[i], i + 1));
		}

		meetingComparator mc = new meetingComparator();
		Collections.sort(meet, mc);
		ArrayList<Integer> ans = new ArrayList<>();
		ans.add(meet.get(0).pos);
		int limit = meet.get(0).end;
		for (int i = 1; i < n; i++) {
			if (meet.get(i).start > limit) {
				limit = meet.get(i).end;
				ans.add(meet.get(i).pos);
			}
		}

		System.out.println(ans);
		return ans.size();
	}
---------------------------------------------------------------------------------
4. Minimum Platforms
Intuition-> we sort both arrays and check whether there is platform needed for any arrival or departure train.
DryRun the code to get better Understanding
 static int findPlatform(int arr[], int dep[], int n)
    { 
       Arrays.sort(arr);
       Arrays.sort(dep);
       
       int plat_needed=1,result=1;
       int i=1,j=0;  //second arrival train and first departure train
       
       while(i<n && j<n){

 //as if train hasn't departured yet then the new arrival train if comes earlier has to use new platform
           if(arr[i]<=dep[j]){
               plat_needed++;  
               i++;
           }else if(arr[i]>dep[j]){
               plat_needed--;
               j++;
           }
           
           if(plat_needed>result)
                result=plat_needed;
       }
        return result;       
    }
---------------------------------------------------------------------------------
5. Minimum Number of coins Needed to make a change
 public static int minCoins(int val){
        ArrayList<Integer>ans=new ArrayList<>();
        int[]den={1,2,5,10,20,50,100,500,1000}; //follows Greedy as sum upto i-1 is smaller than ith element
        int n=den.length;
        for(int i=n-1;i>=0;i--){
            while(val>=den[i]){
                val-=den[i];
                ans.add(den[i]);
            }
        }
        System.out.println(ans);
        return ans.size();
    }
---------------------------------------------------------------------------------
6. Fractional Knapsack
 class itemComparator implements Comparator<Item>{
        @Override
        public int compare(Item a,Item b){
        
        double r1=(double)a.value/(double)a.weight;
        double r2=(double)b.value/(double)b.weight;
        
        if(r1<r2)return 1;
        else if(r1>r2)return -1;
        return 0;
        }
    }
    
    double fractionalKnapsack(int W, Item arr[], int n) 
    {
       Arrays.sort(arr,new itemComparator());
       
       int curr_weight=0;
       double finalans=0.0;
       
       for(int i=0;i<arr.length;i++){
           if(curr_weight+arr[i].weight<=W){
               curr_weight+=arr[i].weight;
               finalans+=arr[i].value;
           }else{
               int remain=W-curr_weight;
               finalans+=(double)arr[i].value/(double)arr[i].weight * (double)remain;
               break;
           }
       }
       return finalans;
    }
---------------------------------------------------------------------------------
7. Maximum product subset of an array
 static int maxProductSubset(int a[], int n) {
        if (n == 1) {
            return a[0];
        }
 
        int max_neg = Integer.MIN_VALUE;
        int count_neg = 0, count_zero = 0;
        int prod = 1;
        for (int i = 0; i < n; i++) {
 
            if (a[i] == 0) {
                count_zero++;
                continue;
            }
 
            if (a[i] < 0) {
                count_neg++;
                max_neg = Math.max(max_neg, a[i]);
            }
 
            prod = prod * a[i];
        }
 
        if (count_zero == n) {
            return 0;
        }

        if (count_neg % 2 == 1) {
 
            // Exceptional case: There is only
            // negative and all other are zeros
            if (count_neg == 1
                    && count_zero > 0
                    && count_zero + count_neg == n) {
                return 0;
            }
 
            // Otherwise result is product of
            // all non-zeros divided by
            //negative number with
            // least absolute value.
            prod = prod / max_neg;
        }
 
        return prod;
    }

---------------------------------------------------------------------------------
8. Huffman Encoding
 static class Node{
        int freq;
        Node left, right;

        Node(int freq){
            this.freq = freq;
            this.left = this.right = null;
        }
    }


    static void preOrder(Node root, String code, ArrayList<String> list){
        if(root == null)
            return;
        if(root.left == null && root.right == null)
            list.add(code);

        preOrder(root.left, code+"0", list);
        preOrder(root.right, code+"1", list);
    }

    static ArrayList<String> huffmanCodes(String S, int[] f, int N){
        PriorityQueue<Node> pq = new PriorityQueue<>(new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                if(o1.freq == o2.freq)
                    return 1;
                return Integer.compare(o1.freq, o2.freq);
            }
        });

        for(int i = 0;i < N;i++){
            pq.add(new Node(f[i]));
        }

        while (pq.size() != 1){
            Node first = pq.poll();
            Node second = pq.poll();

            Node newNode = new Node(first.freq + second.freq);

            newNode.left = first;
            newNode.right = second;

            pq.add(newNode);
        }

        ArrayList<String> list = new ArrayList<>();

        Node root = pq.peek();

        preOrder(root, "", list);

        return list;

    }
---------------------------------------------------------------------------------
9. Maximum Trains for which stoppage can be provided.
Logic-> Just like Activity Selection Problem.
Here, in this question we have been given train no. , arrival time, departure time, req platform no.
so we will make an array(Platform) of size (no of platforms) for each no. platform and put -1 in every index.
Make a class(say Trains) which contain arrival time, departure time and platform no. as data members. Now traverse through given 2d array and put all in ArrayList<Trains>Tlist and now sort according to its departure time. and then traverse this Tlist and check if for a given platform train can be stopped or not, if its first time that we have a train for a given platform then just put it in array (Platform) and after that the above condition. if possible then increment the MAXStopage++.
---------------------------------------------------------------------------------
10. Buy Maximum Stocks if i stocks can be bought on i-th day
 public static void MaxStocks(int[]price,int k){
        ArrayList<pair>list=new ArrayList<>();
        for(int i=0;i<price.length;i++){
            list.add(new pair(price[i],i+1));   //stock price ,day
        }
        
        Collections.sort(list);
        
        int stocks=0;
        for(int i=0;i<list.size();i++){
            stocks+=Math.min(list.get(i).second,k/list.get(i).first);
            k-=list.get(i).first*Math.min(list.get(i).second,k/list.get(i).first);
        }
        System.out.println(stocks);
    }
---------------------------------------------------------------------------------
11. Shop in Candy Store
static ArrayList<Integer> candyStore(int candies[],int n,int k){
      Arrays.sort(candies);
      int min=0;
      int c=0;
      int i=0;
      int j=n-1;
      while(i<=j){
           if(c>=n)
             break;
          min+=candies[i];
          c=c+k+1;     //added 1 for bought candy and k for free candy
          i++;
      }
      
      int max=0;
       c=0;
       i=n-1;
      while(i>=0){
           if(c>=n)
             break;
          max+=candies[i];
          c=c+k+1;
          i--;
      }
      
      ArrayList<Integer>list=new ArrayList<>();
      list.add(min);
      list.add(max);
     
     return list;
    }
---------------------------------------------------------------------------------
12. Minimum Cost to cut a board into squares/CHOCOLA - Chocolate (Spoj)
private static int Chocolate(int m, int n, ArrayList<Integer> x, ArrayList<Integer> y) {
		int cost = 0;
		int v_cut = 1;
		int h_cut = 1;
		int i = 0;
		int j = 0;
		Collections.sort(x, Collections.reverseOrder());
		Collections.sort(y, Collections.reverseOrder());
		// we are taking MaxPriceEdge first because initially we have less pieces so
		// increment in total cost will be less,
		// after cutting... the pieces will increase at that time we will be taking
		// MinPriceEdge ->Greedy
		while (i < m && j < n) {
			if (x.get(i) > y.get(j)) {
				cost += v_cut * x.get(i);
				i++;
				h_cut++;
			} else {
				cost += h_cut * y.get(j);
				j++;
				v_cut++;
			}
		}
		while (i <m) {
			cost += v_cut * x.get(i);
			i++;
		}
		while (j < n) {
			cost += h_cut * y.get(j);
			j++;
		}
		return cost;
	}
---------------------------------------------------------------------------------
13. Check if it is possible to survive on Island
->Sunday is holiday.
// function to find the minimum days
    static void survival(int S, int N, int M)
    {
 
        // If we can not buy at least a week
        // supply of food during the first
        // week OR We can not buy a day supply
        // of food on the first day then we
        // can't survive.
        if (((N * 6) < (M * 7) && S > 6) || M > N)
            System.out.println("No");
 
        else {
 
            // If we can survive then we can
            // buy ceil(A/N) times where A is
            // total units of food required.
            int days = (M * S) / N;
 
            if (((M * S) % N) != 0)
                days++;
 
            System.out.println("Yes " + days);
        }
    }
 
---------------------------------------------------------------------------------
14. Maximize sum after K negations  
 public static long maximizeSum(long arr[], int n, int k)
    {
       Arrays.sort(arr);
        for(int i=0;i<arr.length;i++){
            if(arr[i]<0 && k>0){
                arr[i]=-arr[i];
                k--;
            }
        }
        long min=Integer.MAX_VALUE;
        long sum=0;
        
        for(int i=0;i<n;i++){
            sum+=arr[i];
            min=Math.min(min,arr[i]);
        }
        if((k&1)==1)sum-=2*min;
        
       return sum;
    }
---------------------------------------------------------------------------------
15. Maximize sum(arr[i]*i) of an Array -> Very basic Question
int mod = (int)1e9+7;
int Maximize(int arr[], int n)
{
Arrays.sort(arr);

long sum = 0;
for (int i = 0; i < n; i++)
sum = (sum + (long)arr[i] * i) % mod;

return (int)sum;
}
---------------------------------------------------------------------------------
16. Maximum sum of absolute difference of any permutation
Logic-> we take an arraylist and story elements like smaller bigger alternatively to get max absolute diff.
static int MaxSumDifference(Integer []a, int n)
    {
        List<Integer> finalSequence = new ArrayList<Integer>();
    
        Arrays.sort(a);
     
        for (int i = 0; i < n / 2; ++i) {
            finalSequence.add(a[i]);
            finalSequence.add(a[n - i - 1]);
        }
        if (n % 2 != 0)
            finalSequence.add(a[n/2]);
        
        int MaximumSum = 0;
     
        for (int i = 0; i < n - 1; ++i) {
            MaximumSum = MaximumSum + Math.abs(finalSequence.get(i) - finalSequence.get(i + 1));
        }
     
        // absolute difference of last element
        // and 1st element
        MaximumSum = MaximumSum + Math.abs(finalSequence.get(n - 1) - finalSequence.get(0));
  
        return MaximumSum;
    }
---------------------------------------------------------------------------------
17. Maximize sum of consecutive differences in a circular array /Swap and Maximize
-> Just like above Question
 long maxSum(long arr[] ,int n)
    {
        Arrays.sort(arr);
        int i=0;
        int j=n-1;
        int count=0;
        long sum=0;
        
        while(i<j){
            sum+=Math.abs(arr[i]-arr[j]);
            if(count%2==0)
                i++;
            else
                j--;
            count++;    
        }
        sum+=Math.abs(arr[j]-arr[0]);
        return sum;
    }
---------------------------------------------------------------------------------
18. Minimum sum of absolute difference of pairs of two arrays
Logic-> sort both the given arrays and just do sum+=Math.abs(arr[i]-brr[i]);
---------------------------------------------------------------------------------
19. Smallest subset with sum greater than all other elements
In Greedy also we check that sum of elements upto ith element should be smaller than (i+1)th, here also we kinda checked it.
static int minElements(int arr[], int n)
    {
        int halfSum = 0;
        for (int i = 0; i < n; i++)
            halfSum = halfSum + arr[i];
        halfSum = halfSum / 2;
     
         Arrays.sort(arr);
         
        int res = 0, curr_sum = 0;
        for (int i = n-1; i >= 0; i--) {
            curr_sum += arr[i];
            res++;
     
            if (curr_sum > halfSum)        
                return res;
        }
        return res;
    }
---------------------------------------------------------------------------------
20. Smallest number (when sum of digits and no. of digits is given)
 static String smallestNumber(int sum, int dig){
        String str="";
        if(dig*9<sum){
            return "-1";
        }
        
        for(int i=1;i<=dig;i++){
            if(i==dig){
                str=sum+str;
                break;
            }
            
            if(sum>9){
                str="9"+str;
                sum-=9;
            }else{
                int temp=sum-1;
                str=temp+str;
                sum=1;
            }
        }
        return str;
    }
---------------------------------------------------------------------------------
21. Find maximum sum possible equal sum of three stacks
public static int maxSum(int stack1[], int stack2[],int stack3[], int n1, int n2, int n3)
    {
      int sum1 = 0, sum2 = 0, sum3 = 0;
      
      for (int i=0; i < n1; i++)
          sum1 += stack1[i];
      
      for (int i=0; i < n2; i++)
          sum2 += stack2[i];
      
      for (int i=0; i < n3; i++)
          sum3 += stack3[i];
      
      // As given in question, first element is top
      // of stack..
      int top1 =0, top2 = 0, top3 = 0;
      int ans = 0;
      while (true)
      {
          // If any stack is empty
          if (top1 == n1 || top2 == n2 || top3 == n3)
             return 0;
      
          if (sum1 == sum2 && sum2 == sum3)
             return sum1;
          
          if (sum1 >= sum2 && sum1 >= sum3)
             sum1 -= stack1[top1++];
          else if (sum2 >= sum1 && sum2 >= sum3)
             sum2 -= stack2[top2++];
          else if (sum3 >= sum2 && sum3 >= sum1)
             sum3 -= stack3[top3++];
       }
    }
---------------------------------------------------------------------------------
22. Page Faults in LRU
-> Dry Run the Code 
->Page faults occur when they are not in memory 
static int pageFaults(int n, int c, int pages[]) {
		Set<Integer> set = new HashSet<>();
		HashMap<Integer, Integer> map = new HashMap<>(); 

		int pgfault = 0;

		for (int i = 0; i < n; i++) {
			if (set.size() < c) {
				if (!set.contains(pages[i])) {
					pgfault++;
					set.add(pages[i]);
				}
			} else {
				if (!set.contains(pages[i])) {
					pgfault++;
					// checking for Least Recently Used
					int lru = Integer.MAX_VALUE;// min index refers lru
					int val = 0;
					for (Integer s : set) {
						if (map.get(s) < lru) {
							lru = map.get(s);
							val = s;
						}
					}
					set.remove(val);
					set.add(pages[i]);
				}
			}
			map.put(pages[i], i);
		}

		return pgfault;
	}
---------------------------------------------------------------------------------
23. DEFKIN | Defence of a Kingdom (Spoj)
		int t = scn.nextInt();
		while (t-- > 0) {
			int w = scn.nextInt();
			int h = scn.nextInt();
			int n = scn.nextInt();
			int[] x = new int[n + 1];
			int[] y = new int[n + 1];

			for (int i = 0; i < n; i++) {
				x[i] = scn.nextInt();
				y[i] = scn.nextInt();
			}
			x[n] = w + 1;
			y[n] = h + 1;

			if (n == 0) {
				System.out.println(w * h);
				continue;
			}

			Arrays.sort(x);
			Arrays.sort(y);

			int mx = x[0] - 1;
			for (int i = 1; i < x.length; i++) {
				mx = Math.max(mx, x[i] - x[i - 1] - 1);
			}
			int my = y[0] - 1;
			for (int i = 1; i < y.length; i++) {
				my = Math.max(my, y[i] - y[i - 1] - 1);
			}
			int area = mx * my;
			System.out.println(area);
		}
---------------------------------------------------------------------------------
24. DIEHARD - DIE HARD (Spoj)
public static void main(String args[]) {

		int t = scn.nextInt();
		while (t-- > 0) {
			int H = scn.nextInt();
			int A = scn.nextInt();

			int days = 1;
			H += 3;
			A += 2;
			while (H > 0 && A > 0) {

				if (H > 5 && A > 10) {
					H -= 5;
					A -= 10;
					days++;
				} else if (H > 20) {
					H -= 20;
					A += 5;
					days++;
				} else {
					break;
				}
				if (H > 0 && A > 0) {
					days++;
					H += 3;
					A += 2;
				}
			}
			System.out.println(days);
		}

---------------------------------------------------------------------------------
25. Wine trading in Gergovia (Spoj)
		while (true) {
			long n = scn.nextInt();
			if (n == 0) {
				break;
			}
			long ans = 0;
			long val = 0;
			for (int i = 1; i <= n; i++) {
				val += scn.nextInt();
				ans += Math.abs(val);
			}
			System.out.println(ans);
		}
---------------------------------------------------------------------------------
26. ARRANGE - Arranging Amplifiers (Spoj)
-> Read The question properly to know what exactly we have to do 
btw in this question 5 4 6-> if given amplication factors then to maximise it using given formula would be 6 5 4, because (4)^5^6  (^->power ) whether the base is small or not (except for one) the exponent should be larger for larger ans.
	public static void main(String args[]) {
		int t = scn.nextInt();
		while (t-- > 0) {
			int n = scn.nextInt();
			int[] arr = new int[n];

			for (int i = 0; i < arr.length; i++) {
				arr[i] = scn.nextInt();
			}
			Arrays.sort(arr);
			int i = 0;
			for (i = 0; i < n && arr[i] == 1; i++) {
				System.out.print(arr[i] + " ");
			}
			// special case 2^3 < 3^2
			if (i == n - 2 && arr[i] == 2 && arr[i + 1] == 3) {
				System.out.println(arr[i] + " " + arr[i + 1]);
			} else {

				for (int j = n - 1; j >= 0 && arr[j] != 1; j--)
					System.out.print(arr[j] + " ");

				System.out.println();
			}
		}
	}
---------------------------------------------------------------------------------
27. GCJ101BB - Picking Up Chicks (Spoj)
public static void main(String args[]) {
		int T = scn.nextInt();
		int Case = 1;
		while (T-- > 0) {
			int n = scn.nextInt(); // Given no. of chicks
			int k = scn.nextInt(); // Required no of chicks
			int b = scn.nextInt(); // Distance of barn
			int t = scn.nextInt(); // total given time

			int[] pos = new int[n];
			int[] speed = new int[n];
			for (int i = 0; i < pos.length; i++) {
				pos[i] = scn.nextInt();
			}
			for (int i = 0; i < speed.length; i++) {
				speed[i] = scn.nextInt();
			}
			int count = 0, swaps = 0, notPossible = 0;
			for (int i = n - 1; i >= 0; i--) {
				int Reqdis = b - pos[i];
				int dis = speed[i] * t;
				if (dis >= Reqdis) {
					count++; // no of chicks that reached the barn
					if (notPossible > 0)
						swaps += notPossible;
// when suppose some chicks(which are slow,cannot reach to barn) are ahead of a chick which can reach 
//then we will do cummulative swap
				} else
					notPossible++;

				if (count >= k)
					break;
			}
			if (count >= k)
				System.out.println("Case #" + Case + ": " + swaps);
			else
				System.out.println("Case #" + Case + ": IMPOSSIBLE");

			Case++;
		}
	}
---------------------------------------------------------------------------------
28. Maximum sum of (disjoint) pairs with specific difference
->disjoint pair-> (a,b) (c,d)
 public static int maxSumPairWithDifferenceLessThanK(int arr[], int n, int k) 
    {
        Arrays.sort(arr);
        int sum=0;
        int i=n-1;
        
        while(i>0){
            if(arr[i]-arr[i-1]<k){
                sum+=arr[i]+arr[i-1];
                i-=2;
            }else{
                i--;
            }
        }
        return sum;
    }
---------------------------------------------------------------------------------
---------------------------------------------------------------------------------
---------------------------------------------------------------------------------