DEV Community πŸ‘©β€πŸ’»πŸ‘¨β€πŸ’»

Prashant Mishra
Prashant Mishra

Posted on

Greedy

N meetings in one room

Tc: O(NlogN) as we are using MinHeap(PriorityQueue)

class Solution 
{
    //Function to find the maximum number of meetings that can
    //be performed in a meeting room.
    public static int maxMeetings(int start[], int end[], int n)
    {
        // add your code here
        PriorityQueue<MData> q  = new PriorityQueue<>((a,b)-> a.getEnd()-b.getEnd());
        for(int i =0;i<start.length;i++){
            q.add(new MData(start[i],end[i],i));
        }
        int count =0;
        int ps  = -1,pe = -1;
        while(!q.isEmpty()){
            MData m = q.remove();
            if(m.getStart() > pe){
                count ++;
                ps = m.getStart();
                pe = m.getEnd();
            }
        }
        return count;
    } 


}
class MData{
        int start;
        int end;
        int index;
        public MData(int s,int e,int i){
            this.start = s;
            this.end = e;
            this.index =i;
        }
        public int getEnd(){
            return this.end;
        }
        public int getStart(){
            return this.start;
        }
        public int getIndex(){
            return this.index;
        }
    }
Enter fullscreen mode Exit fullscreen mode

Job sequencing problem

TC: O(nlogn)

class Solution
{
    //Function to find the maximum profit and the number of jobs done.
    int[] JobScheduling(Job arr[], int n)
    {
        // Your code here


        int maxDeadline = 0;
        for(int i =0;i<arr.length;i++){
            maxDeadline  = Integer.max(maxDeadline, arr[i].deadline);
        }
         int slots[]  = new int[maxDeadline];
         HashSet<Integer> set = new HashSet<>();
         int result[] = new int[2];
        Arrays.fill(slots,-1);//none of the slots are occupied 

        Arrays.sort(arr,new Comparator<Job>(){
            public int compare(Job a, Job b){
                return b.profit-a.profit;
            }
        });
        // for(int i =0;i<arr.length;i++)
        //     System.out.println(arr[i].deadline);
        int maxJobs = 0;
        int maxProfit =0;
        for(int i =0;i<arr.length;i++){
            int j = arr[i].deadline-1;// we will try to put the job at its deadline
            // if that slot is already occupied by some other jobId then we will decrement
            // the index to see if the ith job can be placed on earlier slots or not
            while(j>=0 && slots[j] !=-1){
                j--;
            }
            //now while loop has exited it can mean only two things
            //either we have found a slot(with index>=0) whose value is -1 (meaning ith job can be place here)
            //or we all the index of the slots from jth to 0th are occupied by other job ids hence
            //we won't be considering this job as it can't be scheduled
            if(j>=0){
                maxProfit+=arr[i].profit;
                maxJobs++;
                slots[j] = arr[i].id; // jth slot is occupied by ith job
            }
        }
        return new int[]{maxJobs,maxProfit};
    }
}

/*
class Job {
    int id, profit, deadline;
    Job(int x, int y, int z){
        this.id = x;
        this.deadline = y;
        this.profit = z; 
    }
}
*/
Enter fullscreen mode Exit fullscreen mode

Minimum Platforms

TC: O(nlogn)

//User function Template for Java

class Solution
{
    //Function to find the minimum number of platforms required at the
    //railway station such that no train waits.
    static int findPlatform(int arr[], int dep[], int n)
    {
        // add your code here
        Arrays.sort(arr);
        Arrays.sort(dep);
        int i =0,j=0;
        int result = 0;
        int currentPlat =0;
        while(i<arr.length && j< dep.length){
            if(arr[i]<=dep[j]){
                i++;
                currentPlat++;
            }
            else if(arr[i] > dep[j]){
                j++;
                currentPlat--;
            }
            result = Integer.max(result,currentPlat);
        }
        return result;

    }

} 

Enter fullscreen mode Exit fullscreen mode

Fractional knapsack using greedy

TC : O(nlogn)

/*
class Item {
    int value, weight;
    Item(int x, int y){
        this.value = x;
        this.weight = y;
    }
}
*/

class Solution
{
    //Function to get the maximum total value in the knapsack.
    double fractionalKnapsack(int W, Item arr[], int n) 
    {
         Arrays.sort(arr,new Comparator<Item>(){
             public int compare(Item a, Item b){
                 double aa  =(double)a.value/(double)a.weight;
                 double bb = (double)b.value/(double)b.weight;
                 return aa > bb ? -1 : 1;
             }
         });
         double result  =0.0;
         int currentW = 0;
         for(Item i : arr){
             if(W>=i.weight+currentW){
                 currentW+=i.weight;
                 result+= i.value;
             }
             else{
                 int remain = W-currentW;
                 result+= ((double)i.value / (double)i.weight) * (double)remain;
                 break;
             }
         }
         return result;
    }
}

Enter fullscreen mode Exit fullscreen mode

Number of coins

Tc: O(N*M) where N is no of coins and M is target or amount

class Solution{

    public int minCoins(int coins[], int M, int V) 
    { 
        // Your code goes here
        int dp[][] = new int[M][V+1];
        for(int row[] : dp) Arrays.fill(row,-1);
        int result  = getCoins(M-1,coins,V,dp);
        return  result==1000000 ? -1 : result ;
    } 
    public int getCoins(int index,int[] coins,int target,int dp[][]){

        if(index==0){
            if(target % coins[index]== 0) return target/coins[index];
            return 1000000;
        }
        if(dp[index][target]!=-1) return dp[index][target];

        int take  = 1000000;
        if(coins[index]<=target){
            take = 1 + getCoins(index,coins,target-coins[index],dp);
        }
        int dontTake = 0 + getCoins(index-1,coins,target,dp);
        return dp[index][target]  = Integer.min(take,dontTake);
    }
}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)

Timeless DEV post...

How to write a kickass README

Arguably the single most important piece of documentation for any open source project is the README. A good README not only informs people what the project does and who it is for but also how they use and contribute to it.

If you write a README without sufficient explanation of what your project does or how people can use it then it pretty much defeats the purpose of being open source as other developers are less likely to engage with or contribute towards it.