18. greedy algorithm

assign greedily 

like sabse kam distribute kro starting mein

bade number last k liye bacha k rakho

we use 2 pointer here

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

if smj ni aara ki konsa stl use kru, u can even solve ques with few varibles also.

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

1. Shortest Job First Problem
2. Jump game 1
3. Jump game 2
4. Job Sequencing problem
5. N Meetings in a room
6. Insert Intervals
7. Min platforms
8. Valid parenthesis
9. Candy
10. Fractional Knapsack

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

Shortest Job First Problem-

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

JUMP GAME-1

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

JUMP GAME-2:

method-1: dp

method-2: recurssion

method-3: ranges

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

JOB SEQUENCING PROBLEM-

job with deadline 'd' day can be completed on any day <='d'

one job is completed within 1 day

only 1 job / day is allowed

greedy- we will perform job with max profit first

            - delay a job to the end days of its deadline

can be optimised further using dsu(graphs)

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

N Meetings in a room-

(a,b,c)=(start,end,meeting no.)

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

INSERT INTERVALS-

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

Min platforms-

brute-

better-

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

Valid parenthesis-

BRUTE-(recurssion)-

time: 3^n

BETTER- use dp(n^2)

OPTIMAL- use range instead of cnt in brute force

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

CANDY-

BRUTE-

( time:O(3n),  space:O(2n) )

BETTER-

(time-2n   &  space-n)

OPTIMAL-(time-N)

(non intutive, learn)

down wale graph mein niche se upar yaani rerverse m jaayenge toh 1 se 6 hoga yaha

lekin kyuki ques m sum pucha hai n ki distribution toh hum upar se niche 1 to 6 bhardiya👽
----------------------------------------------------------------------------------------------------------------------------

FRACTIONAL KNAPSACK-

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