this is for holding javascript data
Alex Varghese edited q5.tex
about 10 years ago
Commit id: 51616dab291c332c82b83a3adb60d3d2099aa456
deletions | additions
diff --git a/q5.tex b/q5.tex
index a50507a..e4a16e8 100644
--- a/q5.tex
+++ b/q5.tex
...
\section{Question 5}
I don't know. The first thing to do is to sort all the m participants by their satisfaction levels $s_j$. $\theta(mlogm)$ time.
Then since we know all the gifts have an intger dollar value associated with it we can search for the largest and smallest value using n time.
Now that we know that all the prizes have integer values and we found the range we can use counting sort to sort all gift values in $\theta(n)$ time.
Since both lists are sorted we only have to look at each prize and each person once.
We first take the first gift and compare it to the first person. Then we follow this procedure:
If $a_j>=s_j$ automatically assign that gift to that person and continue.
If $a_j
If you continue this to completion that means that you have looked at every single person( m comparison) and some fraction of the gifts. If you have looked at each gift that means you assigned all of them and we are done.
If you still have gifts left that means that all the gifts dollar values are smaller than any particular persons satisfication level. So it will be necessary to use more than one gift to satisfy any person.
Now we are only interested in satisfying the most amount of people at this point so we just take the highest value gifts and assign them to the person with the lowest satisfaction level that is still left. So we will iterate through the rest of the gifts and just assign them to the lowest satisfaction people until we run out of gifts.
So this part will take a total of n+m time. For the first part of the algorithm you run through all the people and then when you are left with the gifts that can no longer satisfy one person you just start assigning them to the bottom of the array that contains the people. So you only look at each person once and each gift once. Which means that you only spend m+n time on this part.
So in total the runtime is $mlogm+n+m+n=\theta(mlogm+n)$
