Dinner Delivery Cleanup Problem

Dinner Delivery Cleanup Problem

Dinner Delivery Cleanup Problem – Problem Setup

A company offers dinner for its employees who are working late. The dinner is ordered via delivery.

One day, the admin noticed that the plastic bag for packing and extra condiments were not thrown away after people have taken their food.

Who should be doing the cleanup? The admin suggested the following approach when taking food:

The person taking the last packet of food should clean up the plastic bag and extra condiments.

This seems to be a reasonable approach at first glance. However, if we treat this as an algorithm problem, we can find out the issue with this approach.

Analyzing the Admin Solution

Translating the above approach naively into pseudo code, we have:

On surface, everything looks fine, we will always have someone to cleanup because the for loop would reach the last element of the array.

However, there might be a case where it would fail when executing  person = next(people-taking-food) if there are less people than food packets.

In fact, the pseudo code does not model our setup very well. We should not be iterating through the food, but rather, we should be iterating through the people who are taking the food.

Hence, a better pseudo code would be:

Now the issue with the approach is quite obvious. If people taking the food is less than the number of food packets ordered, we will never hit the condition for clean up.

Mapping the edge case back to real life, it means that someone orders food but forgets to collect, there will be leftover food after everyone has collected. Hence the trash would not be cleared.

Luckily for us, this rarely happens in because usually people who are hungry but didn’t order the food will go and collect leftover food.

A Deterministic Solution

Is there a better algorithm to solve this problem? Yes. One of the ways I can think of is to assign the person beforehand in a deterministic manner when signing up for food order:

Of course, there might be cases where the last person who sign up never showed up during food collection. However, it would be a people management issue instead of an algorithm issue. For an algorithm’s perspective, it has achieved its goal for always having a person assigned to do the cleanup (when at least one person orders, of course).

Cover photo from: https://www.broadsheet.com.au/melbourne/food-and-drink/article/lunch-comes-you-delivery

More interesting pieces like this: Opinion Pieces

Leave a Reply