Assume you are a kind grandparent and going to give your grandchildren some piec

Question

Assume you are a kind grandparent and going to give your grandchildren some pieces of cake. However, you cannot satisfy a child unless the size of the piece he receives is no less than his expected cake size. Different children may have different expected sizes. Meanwhile, you cannot give each child more than one piece. For example, if the children's expected sizes are [1,3,4] and you have two pieces of cake with sizes [1,2], then you could only make one child satisfied. Given the children's expected sizes and the sizes of the cake pieces that you have, how can you make the most children satisfied? Prove that your algorithm is correct

Explanation / Answer

One of the algorithm to satisfy maximum number of children with a given set
of cake sizes is as follows:

Sort the children based on their expectations and sort the cakes as per
their size.Now start allocating cakes based on the expectations in the
sored order from the sorted order of cakes.To prove the correctness we need
a good invariant.In this case the invariant will be the maximum number of
satisafiable requests have been met till the first ith request for the cake.The sorting
has been done to matchc the requirements with the available cake sizes

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---