Suppose there are n student: 1, 2, 3, ..., i, ..., n.
Now, let's say each want slice size to be: t1, t2, ..., ti, ..., tn.
Let's pizza slices be : s1, s2, ..., si, ..., sn.
Now, it can be said that a student ' i ' will accept a slice of pizza ' si ' only if the size of slice is more then ' ti '.
Logic to distribute: what can be done is we can sort the demand i.e ti of students and also sort the size of pizza slices si. Now, Papa Mario can distribute the sorted slices to students sorted demand(smallest to heighest) one by one as they appear in sorted lists. Now, it will only be possible to distribute the slices to make everyone happy, if and only if in sorted lists of both s and t for each index k, it holds the condition: tk <= sk.
Let me explain you with example:
Lets says size of whole pizza is 100.
Now number of students n = 4.
Let there demands be : 20, 35, 15, 10.
This means 1st student atleast require the slice size of 20 and so on.
Case 1: Papa Mario divides the pizza into slices of size: 25, 20, 20, 35.
=> Now, we sort both lists.
Thus t => 10, 15, 20, 35
and s => 20, 20, 25, 35
Now, as we can see that for all index tk <= sk, hence pizza can be distrubeted so that everyone can be happy.
Case 2: Papa Mario divides the pizza into slices of size: 30, 20, 20, 30.
=> Now, we sort both lists.
Thus t => 10, 15, 20, 35
and s => 20, 20, 30, 30
Now, as we can see that, for last student with demand of 35, the pizza slice alotted is of size 30, thus he is unhappy, and pizza cannot be distributed so that everyone becomes happy.
Now, after the approach, let's discuss question.
(a) Greedy algorithm paradigm is most appropriate for this problem, as what we are doing is greedily distributing small slices to those students which have least demands first then tackling bigger demands of students, by remaining bigger slices.
(b) As we are mainly sorting thel ist of sizes of pizza slices and student demands, thus we need to use an efficient algorithm to sort the lists. Such an efficient algorithm can be QuickSort() or MergeSort().
(c) Asymptotic running time of our algorithm would be O(n*logn).
