- Assign Cookies
- Lemonade Change
- Shortest job first
- Jump game I
- Jump game II
- N meetings in a room
- Activity problem
- Non Overlapping Intervals
- Minimum Number of arrows to burst balloons
- Insert Intervals
- Job sequencing problem
- Minimum Platforms
- Fractional knapsack using greedy
- Number of coins
- Merge Intervals
Using Monotonic stack
Assign Cookies
TC: O(n) where n is the no. of greed/children
class Solution {
public int findContentChildren(int[] g, int[] s) {
//sort both the greed 'g' and size 's' array in ascending order
//if the greed 'i'th is less than or equal to the 'j'th size then it can be satisfied else no greed (k, where k>i) will be satisfied with the current size 'j' ( since the greeds are sorted in ascending order)
//and we have to move to the next size 'j+1' to check the same
Arrays.sort(g);
Arrays.sort(s);
int count =0;
int i= 0,j = 0;
while(i<g.length && j<s.length){
if(g[i]<=s[j]){
count++;
i++;
j++;
}
else{
j++;
}
}
return count;
}
}
Lemonade Change
TC: O(n)
class Solution {
public boolean lemonadeChange(int[] bills) {
int five = 0;
int ten =0;
int twenty = 0;
for(int i = 0;i<bills.length;i++){
if(bills[i] == 5) five++;
else if(bills[i] ==10 && five>0){
five--;
ten++;
}
else if(bills[i] == 20 && ten>0 && five>0){
twenty++;
ten--;
five--;
}
else if(bills[i] ==20 && five>2){
five = five-3;
}
else return false;
}
return true;
}
}
Shortest job first (sjf)
TC: O(nlogn)
class Solution {
static int solve(int bt[] ) {
//shorted job first
Arrays.sort(bt);
//example :
/*
n = 5
bt = [4,3,7,1,2]
after sorting : bt[] = [1,2,3,4,7] = [p4,p5,p2,p1,p3]
p4 p5 p2 p1 p3
0---1------3--------6----------10-------------------17
waiting time for p4 : 0, p5 :1, p2: 3,p1: 6, p3 : 10
total average waiting time : 20/5 = 4
*/
int time = 0;
int wt = 0;
for(int i =0;i<bt.length-1;i++){
time+=bt[i];
wt+=time;
}
return wt/bt.length;
}
}
Jump Game I
TC: O(n), SC: O(1)
class Solution {
static int canReach(int[] A, int N) {
//observations: if the array does not have 0, in that case we can alwys reach to last index
//because we can always keep on jumpting till we reach the last index)
/*
Undersatnding with example :
N = 6
A[] = {1, 2, 0, 3, 0, 0}
let maxIndex = 0;
at index 0 max jump possible is 0+1 = 1 ( index+value = next index that can be raeched), making maxIndex = 1
at index 1 maxjump possible is 1+2 = 3, making maxIndex = 3
at index 2 maxjump possible is 0+0 = 0, maxIndex remains same
at index 3 maxjump possible is 3+3 = 6, maxIndex = 6 > N-1, hence possible to reach the last index
*/
int maxIndex = 0;
for(int i = 0;i<N;i++){
if(i > maxIndex) return 0;
maxIndex = Math.max(maxIndex,i+ A[i]);
if(maxIndex >=N-1) return 1;// early exit
}
return 1;
}
}
Jump Game II
//dp approach:
class Solution {
public int jump(int[] nums) {
int dp[] = new int[nums.length];
Arrays.fill(dp,-1);
return min(0,nums,dp);
}
public int min(int index ,int nums[], int dp[]){
if(index >= nums.length-1) return 0;
if(dp[index]!=-1) return dp[index];
int min = 10001;
for(int jump =1;jump<=nums[index];jump++){
min =Integer.min(min, 1 + min(index+jump, nums,dp));
}
return dp[index] = min;
}
}
A better Greedy appprach:
TC :O(n), sc :O(1)
/*
TC: O(n), outer loop is just for checking if r<n-1, inner loop is doing the
traversal for n elements
This is greedy because in every iteration we are trying to find out the farthest index that we can jump to.
example :
nums = [2,3,1,1,4]
for the index 0 , we can jump to index 1 or we can jump to index 2
So range for the first jump (jump = 1) becomes index: 1,2
from index 1 we can jump to index 2,3,4 ( if we jump to index 2 jump = 2, if we jump to index 3 jump = 2 and if we jump to index 4
jump =2, so we want to minimize the countOfJump and maximize the range of jump which is index 4 in this case)
We can have left and right pointer intialized with 0, then we can iterate left till right to find the max index that can be reached, then
update left and right to point to new range
Do it till the n-1 index is reached
*/
class Solution {
public int jump(int[] nums) {
int left =0,right =0;
int jump = 0;
while(right<nums.length-1){
int farthest = 0;
for(int i =left;i<=right;i++){
farthest = Integer.max(farthest, i+ nums[i]);
}
//now update left and right to point to new range
left = right+1;
right =farthest;
jump++;
}
return jump;
}
}
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;
}
}
Activity problem ( same as N meetings)
TC :O(nlogn)
class Solution
{
public static int activitySelection(int start[], int end[], int n)
{
// add your code here
PriorityQueue<Activity> q = new PriorityQueue<>((a,b)-> a.end-b.end); //acitivites are sorted on the basis of end time
for(int i =0;i<n;i++){
q.add(new Activity(start[i],end[i]));
}
int count = 0;
int previousEndTime = -1;// previousEndTime initialized with -1;
while(!q.isEmpty()){
Activity a = q.remove();
//an activity can only be done if the it's start time is greater than the end time of previuos activity
if(previousEndTime < a.start){
count++;
previousEndTime = a.end;
}
}
return count;
}
}
class Activity{
int start;
int end;
public Activity(int s, int e){
start = s;
end = e;
}
}
Non Overlapping Intervals (same as n meetings in a room)
//we can directly sort the intervals array and iterate over it, //instead of using Queue.
class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
//same as N meetings/no. of activities
//sort the intervals based on end time of each pair
Queue<Pair<Integer,Integer>> q = new PriorityQueue<>((a,b)->a.getValue()-b.getValue());
for(int i = 0;i<intervals.length;i++){
q.add(new Pair(intervals[i][0], intervals[i][1]));
}
int previousEndTime = Integer.MIN_VALUE;
int count = 0;
while(!q.isEmpty()){
Pair<Integer,Integer> p = q.remove();
int start = p.getKey();
int end = p.getValue();
if(start>=previousEndTime){
count++;
previousEndTime = end;
}
}
return intervals.length-count;
}
}
Minimum Number of arrows to burst balloons (same as n meetings in a room
class Solution {
public int findMinArrowShots(int[][] points) {
// this is same as non-overlapping intervals/n meetings in a room/maximum activities problem
//sort the given array based on increasing xend co-ordinates and find out all the non-overlapping interval
Arrays.sort(points,(a,b)->Integer.compare(a[1],b[1]));
long previousEnd = Long.MIN_VALUE;
int count =0;
for(int i =0;i<points.length;i++){
// check if the Xstart of current baloon is greater than the previous ballon's Xend
if(previousEnd < points[i][0]){
count++;
previousEnd = points[i][1];
}
}
return count;
}
}
Insert Intervals
TC: O(n), SC:O(n) for using the list
class Solution {
public int[][] insert(int[][] intervals, int[] newInterval) {
int start = newInterval[0], end = newInterval[1];
if(intervals.length==0) return new int[][]{{start,end}};
List<Pair<Integer,Integer>> list = new ArrayList<>();
int i=0;
while(i < intervals.length){
if(intervals[i][1] < start){ // if the start time of newInterval is greater than the end time of current array, they are not overlapping
list.add(new Pair(intervals[i][0],intervals[i][1]));
}
else{ // overlapping intervals
start = Integer.min(start, intervals[i][0]); //start will be the min of both intervals[i][0] or newIntervals[0]
//now finding the end time
while(i< intervals.length && end >= intervals[i][0] ){ //as long as end time is overlapping with start time of next intervals keep going ahead
end = Integer.max(end, intervals[i][1]);//since the start time of next intervals is overlapping with the 'end', it will be udpated as end = Integer.max(end, intervals[i][1])
//i.e final end time will be the max end time between the 'end' and intervals[i][1]
i++;
}
//finally we have new (start, end);
list.add(new Pair(start,end));
// if still some intervals are remaining in the intervals array add them in the list as well
while(i< intervals.length){
list.add(new Pair(intervals[i][0],intervals[i][1]));
i++;
}
}
i++;
}
// edge case what if the newIntervals are not overlapping at all, then they will satisfy the below condition
//newIntervals start time will be greater than the end time of last intervals[i][1]
if(start > intervals[intervals.length-1][1]) list.add(new Pair(start,end));
return getArray(list);
}
public int[][] getArray(List<Pair<Integer,Integer>> list){
int arr[][] = new int[list.size()][2];
int index = 0;
for(Pair<Integer,Integer> p : list){
arr[index][0] = p.getKey();
arr[index++][1] = p.getValue();
}
return arr;
}
}
a way to understand the same problem
class Solution {
public int[][] insert(int[][] intervals, int[] newInterval) {
List<int[]> list = new ArrayList<>();
int i = 0,n = intervals.length;
//left part
while(i<n && intervals[i][1] < newInterval[0]){
list.add(intervals[i]);
i++;
}
//overlapping part
while(i<n && intervals[i][0] <= newInterval[1]){
newInterval[0] = Integer.min(newInterval[0],intervals[i][0]);
newInterval[1] = Integer.max(newInterval[1],intervals[i][1]);
i++;
}
list.add(newInterval);
//right part
while(i<n){
list.add(intervals[i]);
i++;
}
int result[][] = new int[list.size()][2];
for(i=0;i<list.size();i++){
result[i] = list.get(i);
}
return result;
}
}
or
class Solution {
public int[][] insert(int[][] intervals, int[] newInterval) {
//sort them on the basis of before, overlappingintervals and after
List<int []> before = new ArrayList<>();
List<int[]> after = new ArrayList<>();
for (int [] a : intervals){
if(a[1] < newInterval[0]) before.add(a);
else if (newInterval[1] < a[0]) after.add(a);
else{
newInterval[0] = Math.min(newInterval[0],a[0]);
newInterval[1] = Math.max(newInterval[1],a[1]);
}
}
int result [][]= new int[before.size()+1 + after.size()][2];
int index =0;
for(int i =0;i< before.size();i++){
result[index] = before.get(i);
index++;
}
result[index++] = newInterval;
for(int i =0;i< after.size();i++){
result[index] = after.get(i);
index++;
}
return result;
}
}
Job sequencing problem
TC: O(nlogn)
class Solution
{
//greedy approach:Sort jobs based on the profit in descending order and try to perform jobs as close to their deadline as possible
///if the a job with deadline x can not be performed on day x try to perform it on day x-1, else x-2,...0
int[] JobScheduling(Job arr[], int n)
{
Arrays.sort(arr,(a,b)->b.profit-a.profit);
int maxDeadline = -1;
for(Job job : arr){
maxDeadline = Integer.max(maxDeadline, job.deadline);
}
int slots[] = new int[maxDeadline];//max no. of days available
int noOfjobs =0;
int maxProfit= 0;
Arrays.fill(slots,-1);
for(int i =0;i<arr.length;i++){
for(int j = arr[i].deadline-1;j>=0;j--){//try execute the job as close to its deadline as possible
if(slots[j]==-1){// if the day is available
noOfjobs++;
maxProfit+=arr[i].profit;// get the profit of the ith job
slots[j] = arr[i].id;// get the id of the ith job and put in jth slot/day
break;// since the job has been allocated exit now
}
}
}
return new int[]{noOfjobs,maxProfit};
}
}
/*
class Job {
int id, profit, deadline;
Job(int x, int y, int z){
this.id = x;
this.deadline = y;
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)
{
// 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;
}
}
our using the PriorityQueue or Min Heap
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[]) {
// add your code here
Queue<Integer> q = new PriorityQueue<>();
q.add(-1);// lets assume a train will depart at -1 from ( as we need atleat 1 platform)
Queue<Train> queue = new PriorityQueue<>((a,b)-> a.a-b.a);
for(int i =0;i<arr.length;i++){
queue.add(new Train(arr[i], dep[i]));
}
while(!queue.isEmpty()){
Train t = queue.remove();
// if the arrival time of next train is greater the departure time of the train that is going to leave the station first (before any other train on the platform)
if(t.a > q.peek()) q.remove(); // same platform can be utilized
q.add(t.d); // or another platform will be needed
}
return q.size();// no. of plaform
}
}
class Train{
int a;
int d;
public Train(int a, int d){
this.a =a;
this.d = d;
}
}
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) {
Queue<Item> q = new PriorityQueue<>((a,b)-> Double.compare((double)b.value/(double)b.weight,(double)a.value/(double)a.weight));
for(int i =0;i<arr.length;i++){
q.add(arr[i]);
}
double profit = 0.0;
while(!q.isEmpty()){
Item i = q.remove();
if(w>=i.weight){
w = w-i.weight;
profit+=i.value;
}
else{
profit+= (double)(((double)i.value/(double)i.weight)*(w));
w = 0;// or break;
}
}
return profit;
}
}
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);
}
}
Top comments (0)