# 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)
{
PriorityQueue<MData> q  = new PriorityQueue<>((a,b)-> a.getEnd()-b.getEnd());
for(int i =0;i<start.length;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;
}
}
``````

# 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)
{

for(int i =0;i<arr.length;i++){
}
HashSet<Integer> set = new HashSet<>();
int result[] = new int;
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++)
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 {
Job(int x, int y, int z){
this.id = x;
this.profit = z;
}
}
*/
``````

# 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)
{
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;

}

}

``````

# 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;
}
}

``````

# 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)
{
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);
}
}
``````