First Fit vs Best Fit A restaurant has 4 tables of sizes 5, 4, 6, and 7 seats wi

Question

First Fit vs Best Fit

A restaurant has 4 tables of sizes 5, 4, 6, and 7 seats with table number 1, 2, 3, and 4 respectively. If a party of 4 comes in with all the tables empty, they will be lead to table 1 for first fit and to table 2 for best fit. Suppose that guests of different parties can sit in the same table but a party can not be split to sit in more than one table.

(a)(5%) Now do these questions with some data changed. We have a restaurant with 10 tables of sizes 3, 4, 5, 3, 4, 5, 3, 10, 7, 4. Explain what happens when 4 guest parties of 3, 4, 6, and 7 come in, how will first fit seat the guests and how will best fit seat the guests.

(b)(5%) What if the guests come in the order of 7, 6, 5, and 4 guests (for first fit and for best fit?

(c)(5%) What if the guests come in the order of 2, 2, 2, 2, 2, and 2 (6 parties of 2 guests each)?

(d)(10%) Can you find a restaurant with tables and also guests order that best fit is better than first fit?

(e)(10%) Can you find a restaurant with tables and also guests order that first fit is better than best fit?

Explanation / Answer

a
T1{3} T2{4} T3{5} T4{3} T5{4} T6{5} T7{3} T8{10} T9{7} T10{4}
FIRST FIT:
GUEST OF SIZE 3 comes in. Table allocated T1. so new status:
T1{0} T2{4} T3{5} T4{3} T5{4} T6{5} T7{3} T8{10} T9{7} T10{4}

GUEST OF SIZE 4 comes in. Table allocated T2. so new status:
T1{0} T2{0} T3{5} T4{3} T5{4} T6{5} T7{3} T8{10} T9{7} T10{4}

GUEST OF SIZE 6 comes in. Table allocated T8. so new status:
T1{0} T2{0} T3{5} T4{3} T5{4} T6{5} T7{3} T8{4} T9{7} T10{4}

GUEST OF SIZE 7 comes in. Table allocated T9. so new status:
T1{0} T2{0} T3{5} T4{3} T5{4} T6{5} T7{3} T8{4} T9{0} T10{4}

BEST FIT:

GUEST OF SIZE 3 comes in. Table allocated T1. so new status:
T1{0} T2{4} T3{5} T4{3} T5{4} T6{5} T7{3} T8{10} T9{7} T10{4}

GUEST OF SIZE 4 comes in. Table allocated T2. so new status:
T1{0} T2{0} T3{5} T4{3} T5{4} T6{5} T7{3} T8{10} T9{7} T10{4}

GUEST OF SIZE 6 comes in. Table allocated T9. so new status:
T1{0} T2{0} T3{5} T4{3} T5{4} T6{5} T7{3} T8{10} T9{1} T10{4}

GUEST OF SIZE 7 comes in. Table allocated T8. so new status:
T1{0} T2{0} T3{5} T4{3} T5{4} T6{5} T7{3} T8{3} T9{1} T10{4}

b
T1{3} T2{4} T3{5} T4{3} T5{4} T6{5} T7{3} T8{10} T9{7} T10{4}
FIRST FIT:
GUEST OF SIZE 7 comes in. Table allocated T8. so new status:
T1{3} T2{4} T3{5} T4{3} T5{4} T6{5} T7{3} T8{3} T9{7} T10{4}
GUEST OF SIZE 6 comes in. Table allocated T1. so new status:
T1{3} T2{4} T3{5} T4{3} T5{4} T6{5} T7{3} T8{3} T9{1} T10{4}
GUEST OF SIZE 5 comes in. Table allocated T3. so new status:
T1{3} T2{4} T3{0} T4{3} T5{4} T6{5} T7{3} T8{3} T9{1} T10{4}
GUEST OF SIZE 4 comes in. Table allocated T2. so new status:
T1{3} T2{0} T3{0} T4{3} T5{4} T6{5} T7{3} T8{3} T9{1} T10{4}

BEST FIT:
GUEST OF SIZE 7 comes in. Table allocated T9. so new status:
T1{3} T2{4} T3{5} T4{3} T5{4} T6{5} T7{3} T8{10} T9{0} T10{4}
GUEST OF SIZE 6 comes in. Table allocated T8. so new status:
T1{3} T2{4} T3{5} T4{3} T5{4} T6{5} T7{3} T8{4} T9{0} T10{4}
GUEST OF SIZE 5 comes in. Table allocated T3. so new status:
T1{3} T2{4} T3{0} T4{3} T5{4} T6{5} T7{3} T8{4} T9{0} T10{4}
GUEST OF SIZE 4 comes in. Table allocated T2. so new status:
T1{3} T2{0} T3{0} T4{3} T5{4} T6{5} T7{3} T8{3} T9{1} T10{4}

c
T1{3} T2{4} T3{5} T4{3} T5{4} T6{5} T7{3} T8{10} T9{7} T10{4}
FIRST FIT:
GUEST OF SIZE 2 comes in. Table allocated T1. so new status:
T1{1} T2{4} T3{5} T4{3} T5{4} T6{5} T7{3} T8{10} T9{7} T10{4}
GUEST OF SIZE 2 comes in. Table allocated T2. so new status:
T1{1} T2{2} T3{5} T4{3} T5{4} T6{5} T7{3} T8{10} T9{7} T10{4}
GUEST OF SIZE 2 comes in. Table allocated T3. so new status:
T1{1} T2{0} T3{3} T4{3} T5{4} T6{5} T7{3} T8{10} T9{7} T10{4}
GUEST OF SIZE 2 comes in. Table allocated T3. so new status:
T1{1} T2{0} T3{1} T4{3} T5{4} T6{5} T7{3} T8{10} T9{7} T10{4}
GUEST OF SIZE 2 comes in. Table allocated T4. so new status:
T1{1} T2{0} T3{1} T4{1} T5{4} T6{5} T7{3} T8{10} T9{7} T10{4}

BEST FIT:
GUEST OF SIZE 2 comes in. Table allocated T1. so new status:
T1{1} T2{4} T3{5} T4{3} T5{4} T6{5} T7{3} T8{10} T9{7} T10{4}
GUEST OF SIZE 2 comes in. Table allocated T4. so new status:
T1{1} T2{4} T3{5} T4{1} T5{4} T6{5} T7{3} T8{10} T9{7} T10{4}
GUEST OF SIZE 2 comes in. Table allocated T7. so new status:
T1{1} T2{4} T3{5} T4{1} T5{4} T6{5} T7{1} T8{10} T9{7} T10{4}
GUEST OF SIZE 2 comes in. Table allocated T2. so new status:
T1{1} T2{2} T3{5} T4{1} T5{4} T6{5} T7{1} T8{10} T9{7} T10{4}
GUEST OF SIZE 2 comes in. Table allocated T2. so new status:
T1{1} T2{0} T3{5} T4{1} T5{4} T6{5} T7{1} T8{10} T9{7} T10{4}
GUEST OF SIZE 2 comes in. Table allocated T5. so new status:
T1{1} T2{0} T3{5} T4{1} T5{2} T6{5} T7{1} T8{10} T9{7} T10{4}

d: Best fit would be better if
Table sizes are 6 2 2 and guest of size 2 comes then guest of size 5 comes. In first fit we cannot solve the problem.

e: First fit is better when

Table sizes are 5 3 3 and guest comes in order 2 3 3 3: in first fit guest of size 2, 3 will be alocated table 1 of size 5 and remaining two will be allocated tables of size 3 ie
2-->5
3-->5
3-->3
3-->3

but in best fit
2--> 3
3--> 3
3--> 5
3 cannot be allocated!!

I hope this answer helped you :)

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

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