Priority Queues

LexicographicallySmallestStringPossibleByUsingGivenOperations.java

// https://www.geeksforgeeks.org/lexicographically-smallest-string-possible-by-using-given-operations/
// Given a string S consisting of digits from 0 to 9 inclusive, the task is to form the lexicographically
// smallest string by performing an operation any number of times. In one operation you can choose any
// position i and delete the digit d at s[i] and insert min(d+1, 9) on any position (at the beginning,
// at the end, or in between any two adjacent digits).

import java.io.*;
import java.util.*;
import java.util.PriorityQueue;

public class Gfg {

    public static String smallestString(String s, int n) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        int lastDigit = s.charAt(n - 1) - '0';
        pq.offer(lastDigit);

        for (int i = n - 2; i >= 0; i--) {
            int value = s.charAt(i) - '0';
            if (value > lastDigit) {
                int mini = Math.min(value + 1, 9);
                pq.offer(mini);
            } else {
                lastDigit = value;
                pq.offer(value);
            }
        }

        StringBuilder ans = new StringBuilder();
        while (!pq.isEmpty()) {
            ans.append(pq.poll());
        }

        return ans.toString();
    }

    public static void main(String[] args) {
        String s = "04829";
        int n = s.length();
        System.out.println(smallestString(s, n));

        s = "07";
        n = s.length();
        System.out.println(smallestString(s, n));
    }
}

MaximumNumberOfDiamondsThatCanBeGainedInKMinutes.java

// Given an array arr[] consisting of N positive integers such that arr[i] 
// represents that the ith bag contains arr[i] diamonds and a positive integer K, 
// the task is to find the maximum number of diamonds that can be gained in exactly 
// K minutes if dropping a bag takes 1 minute such that if a bag with P diamonds 
// is dropped, then it changes to [P/2] diamonds, and P diamonds are gained.

import java.util.*;

class GFG {

    // Function to find the maximum number
    // of diamonds that can be gained in
    // exactly K minutes
    static void maxDiamonds(int A[], int N, int K) {

        // Stores all the array elements
        PriorityQueue<Integer> pq = new PriorityQueue<>(
                (a, b) -> b - a);

        // Push all the elements to the
        // priority queue
        for (int i = 0; i < N; i++) {
            pq.add(A[i]);
        }

        // Stores the required result
        int ans = 0;

        // Loop while the queue is not
        // empty and K is positive
        while (!pq.isEmpty() && K-- > 0) {

            // Store the top element
            // from the pq
            int top = pq.peek();

            // Pop it from the pq
            pq.remove();

            // Add it to the answer
            ans += top;

            // Divide it by 2 and push it
            // back to the pq
            top = top / 2;
            pq.add(top);
        }

        // Print the answer
        System.out.print(ans);
    }

    // Driver Code
    public static void main(String[] args) {
        int A[] = { 2, 1, 7, 4, 2 };
        int K = 3;
        int N = A.length;

        maxDiamonds(A, N, K);
    }
}

// This code is contributed by 29AjayKumar

MeetingRooms.java

// https://leetcode.com/problems/meeting-rooms/
// Given an array of meeting time intervals where intervals[i] = [starti, endi], determine if a person could attend all meetings.

class Solution {
    public boolean canAttendMeetings(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        for (int i = 0; i < intervals.length - 1; i++) {
            if (intervals[i][1] > intervals[i + 1][0]) {
                return false;
            }
        }
        return true;
    }
}

PriorityQueueReverseOrder.java

// Java program to demonstrate the
// working of PriorityQueue in reverse order
import java.util.*;

class PriorityQueueDemo {

    // Main Method
    public static void main(String args[]) {
        // Creating empty priority queue
        PriorityQueue<Integer> pQueue = new PriorityQueue<Integer>(
                Collections.reverseOrder());

        // Adding items to the pQueue using add()
        pQueue.add(10);
        pQueue.add(20);
        pQueue.add(15);
        pQueue.add(5);

        // Printing the top element of PriorityQueue
        System.out.println(pQueue.peek());

        // Printing the top element and removing it
        // from the PriorityQueue container
        System.out.println(pQueue.poll());

        // Printing the top element again
        System.out.println(pQueue.peek());
    }
}

PriorityQueueThroughComparator.java

// Java program to demonstrate working of
// comparator based priority queue constructor
import java.util.*;

public class Example {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // Creating Priority queue constructor having
        // initial capacity=5 and a StudentComparator instance
        // as its parameters
        PriorityQueue<Student> pq = new PriorityQueue<Student>(5, new StudentComparator());

        // Invoking a parameterized Student constructor with
        // name and cgpa as the elements of queue
        Student student1 = new Student("Nandini", 3.2);

        // Adding a student object containing fields
        // name and cgpa to priority queue
        pq.add(student1);
        Student student2 = new Student("Anmol", 3.6);
        pq.add(student2);
        Student student3 = new Student("Palak", 4.0);
        pq.add(student3);

        // Printing names of students in priority order,poll()
        // method is used to access the head element of queue
        System.out.println("Students served in their priority order");

        while (!pq.isEmpty()) {
            System.out.println(pq.poll().getName());
        }
    }
}

class StudentComparator implements Comparator<Student> {

    // Overriding compare()method of Comparator
    // for descending order of cgpa
    public int compare(Student s1, Student s2) {
        if (s1.cgpa < s2.cgpa)
            return 1;
        else if (s1.cgpa > s2.cgpa)
            return -1;
        return 0;
    }
}

class Student {
    public String name;
    public double cgpa;

    // A parameterized student constructor
    public Student(String name, double cgpa) {

        this.name = name;
        this.cgpa = cgpa;
    }

    public String getName() {
        return name;
    }
}

SuperUglyNumber.java

// https://www.geeksforgeeks.org/super-ugly-number-number-whose-prime-factors-given-set/
// Super ugly numbers are positive numbers whose all prime factors are in the given prime list. Given a number n, the task is to find the nth Super Ugly number.
// It may be assumed that a given set of primes is sorted. Also, the first Super Ugly number is 1 by convention.

import java.util.*;

class Main {
    public static void main(String[] args) {
        int[] primes = { 2, 5 };
        int k = primes.length;
        int n = 5;
        System.out.println(superUgly(n, primes, k));
    }

    // Function to get the nth super ugly number
    // primes[] --> given list of primes f size k
    // ugly --> set which holds all super ugly
    // numbers from 1 to n
    // k --> Size of prime[]
    public static int superUgly(int n, int[] primes, int k) {
        // nextMultiple holds multiples of given primes
        int[] nextMultiple = Arrays.copyOf(primes, k);

        // To store iterators of all primes
        int[] multiple_Of = new int[k];
        Arrays.fill(multiple_Of, 0);

        // Create a set to store super ugly numbers and
        // store first Super ugly number
        Set<Integer> ugly = new HashSet<>();
        ugly.add(1);

        // loop until there are total n Super ugly numbers
        // in set
        while (ugly.size() != n) {
            // Find minimum element among all current
            // multiples of given prime
            int next_ugly_no = Integer.MAX_VALUE;
            for (int i = 0; i < k; i++) {
                next_ugly_no = Math.min(next_ugly_no,
                        nextMultiple[i]);
            }

            // insert this super ugly number in set
            ugly.add(next_ugly_no);

            // loop to find current minimum is multiple
            // of which prime
            for (int j = 0; j < k; j++) {
                if (next_ugly_no == nextMultiple[j]) {
                    // increase iterator by one for next
                    // multiple of current prime
                    multiple_Of[j]++;

                    // this loop is similar to find
                    // dp[++index[j]] it --> dp[++index[j]]
                    List<Integer> uglyList = new ArrayList<>(ugly);
                    int it = uglyList.get(multiple_Of[j] - 1);
                    nextMultiple[j] = primes[j] * it;
                    break;
                }
            }
        }

        // n'th super ugly number
        List<Integer> uglyList = new ArrayList<>(ugly);
        return uglyList.get(uglyList.size() - 1);
    }
}

// This code is contributed by divyansh2212

TakeGiftsFromTheRichestPile.java

// https://leetcode.com/problems/take-gifts-from-the-richest-pile/
// You are given an integer array gifts denoting the number of gifts in various piles. Every second, you do the following:

// Choose the pile with the maximum number of gifts.
// If there is more than one pile with the maximum number of gifts, choose any.
// Leave behind the floor of the square root of the number of gifts in the pile. Take the rest of the gifts.
// Return the number of gifts remaining after k seconds.

class Solution {
    public long pickGifts(int[] gifts, int k) {
        Arrays.sort(gifts);
        for (int i = gifts.length - 1, j = 1; j <= k; j++) {
            if (gifts[i] == 1) {
                break;
            }
            int p = (int) (Math.sqrt(gifts[i]));
            gifts[i] = p;
            Arrays.sort(gifts);
        }
        long s = 0;
        for (int i : gifts) {
            s += (long) i;
        }
        return s;
    }
}

UglyNumbers.java

// https://www.geeksforgeeks.org/ugly-numbers/
// Ugly numbers are numbers whose only prime factors are 2, 3 or 5.
// The sequence 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, … shows the first 11 ugly numbers.
// By convention, 1 is included. 
// Given a number n, the task is to find n’th Ugly number.

// Java program to find nth ugly number
import java.lang.Math;
import java.io.*;

class UglyNumber {
    // Function to get the nth ugly number
    int getNthUglyNo(int n) {
        // To store ugly numbers
        int ugly[] = new int[n];
        int i2 = 0, i3 = 0, i5 = 0;
        int next_multiple_of_2 = 2;
        int next_multiple_of_3 = 3;
        int next_multiple_of_5 = 5;
        int next_ugly_no = 1;

        ugly[0] = 1;

        for (int i = 1; i < n; i++) {
            next_ugly_no = Math.min(next_multiple_of_2,
                    Math.min(next_multiple_of_3,
                            next_multiple_of_5));

            ugly[i] = next_ugly_no;
            if (next_ugly_no == next_multiple_of_2) {
                i2 = i2 + 1;
                next_multiple_of_2 = ugly[i2] * 2;
            }
            if (next_ugly_no == next_multiple_of_3) {
                i3 = i3 + 1;
                next_multiple_of_3 = ugly[i3] * 3;
            }
            if (next_ugly_no == next_multiple_of_5) {
                i5 = i5 + 1;
                next_multiple_of_5 = ugly[i5] * 5;
            }
        }

        // End of for loop (i=1; i<n; i++)
        return next_ugly_no;
    }

    // Driver code
    public static void main(String args[]) {

        int n = 150;

        // Function call
        UglyNumber obj = new UglyNumber();
        System.out.println(obj.getNthUglyNo(n));
    }
}