3.2 KiB
Greedy
k
negations
Given A[N] can have -ve can have 0s k negations can choose same element multiple times find the maximum sum that you can achieve
always find the smallest and negate it
Sort: O(n \log n + k)
Min Heap: O(n+k \log n)
Note: 1 2 will have -1 2 or 1 2 as the final answer can keep toggling the smallest element
What is Greedy
Greedy - when optimal solution to a local problem is also the optimal solution to the global problem
That is, if you can act greedily at every step, and still reach the optimal. If you don't have to think long term to achieve the optimal
Where will greedy not work?
Local solution is not contributing to the global solution
Whenever greedy works, it will be based on observations and intuition
But have to be careful because can be subtle-non-greedy case
Max Sum Subset
Given A[N] with -ves Find the subset of size k with maximum sum
Sort and take top k values
O(n \log n)
Amazon - Min Subset Product
Given A[N] min possible subset product
Examples
-1 -1 -2 4 5 = -24 -1 0 2 = -2 0 1 = 0
- If no -ve, then choose min
\geq 0
- If k -ve, then choose all
> 0
. don't choose 0- if odd -ve, choose all
- if even -ve, choose the smallest odd -ves
O(n)
Activity Selection
Multiple companies. Very important
Incorrect: min sized?
============= ===============
========
Incorrect: start time
Correct: least overlaps?
but easier: first one to end
sort by end time and execute
Proof:
Assume there exists a solution that doesn't include the min end time job.
Add this job. Either it overlaps with 1, or with 0. Optimal in both cases
So, for every optimal solution without the min end job, we also have an optimal solution with the min end job.
So, optimal to always choose the min end job
Flights
start, end time of flights num of platforms
+1 -1, prefix sum max
Job Scheduling + Profit
day deadlines for jobs can perform only 1 job per day
delay the job
O(n \log n + n^2)
n \log n
to sort by profit
n^2
because start at end time and move left to find an empty slot
Can reduce to n log n using BBST
we want the highest number in the set which is less than x we also want to remove any given number from set
set - upperbound - google
Rats and Holes
Rats Holes equal count locations given for each ech rat runs together each must reach a hole max time so that all reach hole
sort, all go left or all go right
cant cross because that will increase time
------- ----------
vs
----------
---------------------------