1. In choosing a toilet stall in a public bathroom, people want privacy and refu

Question

1. In choosing a toilet stall in a public bathroom, people want privacy and refuse to use one adjacent to an occupied stall. So, given a row of n stalls, the first person to arrive will choose an end stall and the second to arrive will choose the opposite end stall. From then on, a anybody arriving makes the greedy choice of the stall furthest away on each side of occupied stalls; if all remaining stalls are adjacent to an occupied stall, the person just leaves. Let U(n) be the maximum number of people that this protocol can service; analyze U(n).

Explanation / Answer

Let say, there are 10 stalls, starting from 1 to 10.

So, according to the given scenario, the occupancy of the stalls will be in order:

1 -> 10 -> 5 -> 3-> 7 , so the total no. of occupancy is 5 i.e 10/2.

Now, let say there are 11 stalls, then occupancy will be in order of

1-> 11-> 6 -> 3 -> 9 , so here also total no. of occupancy is 5 i.e 11/2.

So, if there are N stalls, total no. of occupancy will be N/2.

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.