18. Greedy algorithm

-----------------------------------------------------------------------------------------------------------------------------

1. Assign Cookies

Optimal- time: O(nlogn+mlogm)

using 2.2 Best first pattern

1. use sorting & sort both arrays
2. use two pointers in 2 sorted arrays to track how many cookies can be assigned

-----------------------------------------------------------------------------------------------------------------------------

2. Fractional Knapsack

Optimal- time: O(nlogn)

using 2.2. Best first pattern

1. sort the array as per (val/wt) values in descending order (since we want greedily max values with min weights to fill upto max weight capacity of knapsack)
2. now start taking into account the values as you traverse from start in this sorted array & also keep track of capacity being done so far (if current weight is allowed under capacity, then take whole item for value)
3. When current weight is more than left capacity, then take fractional value of this item as per ratio of remaining capacity and current weight.

---------------------------------------------------------------------------------------------------------------------------

3. Jump Game-I

Observation- if array has no zeros, we can always reach the end
---------------------------------------------
Brute-  time: O(exponential)

using recursion to explore all paths for every index & see if any index can reach end...

-------------------------------------------
Better-  time: O(n^2)  space: O(n)

using DP
---------------------------------------
Optimal- time: O(n)   space: O(1)

using greedy: 2.2 Best first pattern
(instead of checking if current index can reach the end, we will see which is the farthest index we can reach so far)

-----------------------------------------------------------------------------------------------------------------------------

4. Jump Game-II:

Brute- time: O(exponential)
using recursion

------------------------------------------------
Better- time: O(n^2)

using DP
-------------------------------------------------

Optimal: time: O(n)

(non intuitive)
using greedy: 2.2 Best First Pattern

we see what range of positions can we reach in a certain number of jumps
1. in a current range of [l,r], we find what will be next range
2. next L will be (current r +1)  & next R will be farthest we can go from current range

---------------------------------------------------------------------------------------------------------------------------

5. Valid parenthesis string with *

Brute- time: O(exponential)

using recursion
(keep a pointer and a counter, and cnt++ if opening bracket, do cnt-- if closing bracket, and have 3 cases for *)

---------------------------------------------------

Better- time: O(n^2)

use DP
-------------------------------------------------

Optimal- time: O(n)⭐⭐

using greedy- ( Feasibility check pattern )
Non intuitive

- we maintain range instead of count (since * can have 3 options of + - and 0 to count)

----------------------------------------------------------------------------------------------------------------------------

# Corrective Greedy 

(deadlines related problems)

you have to choose the best subset , if many things are competing for a limited time

Approach-
1. sort tasks by constraint
2. assume you take every task
3. keep all chosen tasks in a data structure
4. as you move forward in time, if constraints break, remove worst task from data structure

--------------------------------------------------------------------------------------------------------------

6. Job Sequencing Problem-I

Ques-
given n jobs with each having a deadline & a profit
job with deadline d can be completed on any day <=d

each job completed in 1 day

only 1 job / day
---------------------------------------------------------
using Greedy slot filling: time:O(n^2)

- sort the jobs with profit, in descending order
- now iterate through the array and for each job try to schedule to closest slot to its deadline which is free

--------------------------------------------------------------------------------------------------------------

7. Job Sequencing Problem-II

Ques-
each job has some duration (now it is not that each job is completed in only 1 day)

--------------------------------------------------------
this approach can also work for variant-1 of this problem (just that the heap will only store profits in that case)

using Corrective Greedy: time:O(nlogn)

Concept for variant-1:
at any time d, we have scheduled d jobs till now, hence we use a min heap and after sorting jobs with deadline, we insert each job into queue and the moment heap size is more than current time, then we remove job with least profit from the heap

-----------------------------------------------------
Concept for variant-2:
instead of checking heap size, now we will maintain a total time variable which would add up durations of jobs scheduled till now & check if at any job totaltime exceeds current duration then we remove job with least profit from scheduling thus removing its duration as well

-----------------------------------------------------------------------------------------------------------------------------

8. Shortest job first: SJF-I

- Given execution time of n processes, find min average waiting time, following SJF policy.

- all jobs arrive at time 0
- SJF: execute the process with smallest execution time ; other processes wait till processes with shorter execution time gets executed)
- waiting time for a process = sum of execution times of all previously executed processes
------------------------------

Using Best First Greedy

1. sort the jobs in ascending order of execution times
2. traverse the array and add all prefix waiting times of each job
3. at the end, calculate avg waiting time

----------------------------------------------------------------------------------------------------------------------------

9. Shortest job first: SJF-II

- all jobs arrive at different arrival times

------------------
Now, at a time t, only a set of jobs which have arrived are candidates for scheduling.

1. sort jobs by arrival times
2. iterate the array and for a time t, push all jobs (which have arrived before t) into min heap 
3. now choose shortest execution time job from the min heap & update total waiting time (by adding this job's waiting time) & also update t (by adding burst time of this job)

----------------------------------------------------------------------------------------------------------------------------

# Earliest Finish Greedy Algo-

( template )

we are finding maximum non overlapping intervals in a set of intervals

-----------------------------------------------------------------------------------------------------------------------------

10/11. N Meetings in a room-

Given n meetings each having a start and an end time. Find maximum no. of meetings you can have in a room. Given that only 1 meeting can happen at a time and also that start of any can't be equal to end of other.

or

Given n intervals with start & end time. Find minimum intervals to remove so remaining intervals do not overlap.
------------------------------------------------------------
Approach- using Earliest Finish Greedy

Concept- Pick interval which finishes earliest so leaving max time for other meetings to happen.
1. Sort in ascending order of ending time
2. now iterate through the array and do cnt++ if a meeting's start time do not overlap with previous meeting's end time and then update prev end time correspondingly...

----------------------------------------------------------------------------------------------------------------------------

# Resource Optimisation-

Whenever we are said, we have been given limited resource which is occupied by tasks over time. Then, it means we have to find max no. of active tasks at a time
-----------------------------------------------------------------------------------------------------------------------------

12. Min platforms required-

Given arrival[ ] & departure[ ] time for n trains. Find minimum platforms required, so no train is waiting. (If arrival[B] = departure[A], still both need different platforms)

or, 

find max overlapping intervals

------------------------------------------------
Approach: min platforms required = max trains present at station at any time

Brute- time: O(n^2)

For every train, assume it is currently at the station and count how many other trains are also present at that moment

-------------------------------------------------------
Optimal- time: O(nlogn)

using sorting + two pointers

1. sort both arrays
2. use two pointers along with a counter which increases if at[i] comes first & decreases if dt[j] comes first. Counter's value tells how many trains exist in same time.
3. max value at any instant of this counter is max overlapping intervals during that time

---------------------------------------------------------------------------------------------------------------

13. Merge intervals-

Given n intervals each having a start time and an end time, merge all overlapping intervals.
---------------
Approach-
1. sort the intervals as per starting time
2. if current interval overlaps with previous interval, update previous interval's ending time to max val
3. else, add current interval as a new interval.
----------------

---------------------------------------------------------------------------------------------------------------

14. Insert Intervals-⭐

Given an intervals array which is sorted as per start time & has non overlapping intervals.
Insert a new interval in it. The final result array should still be sorted and should have no overlapping intervals. Also do this stuff, by creating a new array of intervals, instead of modifying given array.

----------------------------------------------------
1. Add intervals which are before new interval
2. Merge overlapping intervals with new interval
3. Add all intervals which are to the right of new interval

-----------------------------------------------------------------------------------------------------------------------------

15. Candy-

Brute-  time:O(n)   space:O(n)

using 2 pass greedy

-----------------------------------------------------
Optimal- time: O(n)    space: O(1)⭐

Using slope concept (non intuitive)
1. imagine a slope drawn for all values of ratings of children (you get different slopes)
2. start with giving 1 candy to 1st child 

3. For increasing slope, just increase candies by 1 for each child
4. For downward slope, do same but from down

5. For peak, take max of both distributions you did

# Trick- since we are not asked about exact distribution, so we do down to up distribution from up to down instead of down to up, to make things easy for us

-----------------------------------------------------------------------------------------------------------------------------