در یک ترمینال تاکسیرانی، تعداد بسیار زیادی تاکسی در یک صف قرار دارند. ظرفیت هر تاکسی دقیقاً ۴ نفر است و هر تاکسی تنها زمانی ترمینال را ترک میکند که دقیقاً ۴ مسافر در آن نشسته باشد.
میدانیم تعداد تاکسیهای موجود در ترمینال (در ابتدای روز) بسیار بسیار زیاد است و مسافرانِ ترمینال در دستههای ۱، ۲، ۳ یا ۴ نفره و در زمانهای مشخص وارد ترمینال میشوند. هر مسافر (در هر دستهای که باشد)، از زمان ورود به ترمینال تا زمانی که تاکسیای که در آن نشسته حرکت کند احساس بیحوصلگی میکند و از این رو، اندازهی این فاصلهی زمانی را «میزان نارضایتی» آن مسافر میگوییم.
برای مثال اگر یک گروه ۳ نفره در زمان ۱۰ و یک گروه ۱ نفره در زمان ۵۰ وارد ترمینال شوند و دو گروه در یک تاکسی بنشینند، مجموع نارضایتی تمام آنها ۱۲۰ میشود.
اکنون از شما خواسته شده تا با دانستن زمان ورود و تعداد افراد دستههای مختلفی که وارد ترمینال میشوند، طوری مسافران را در تاکسیها بنشانید که مجموع نارضایتی تمام مسافران کمینه شود. دقت کنید که تمام اعضای یک گروه باید الزاماً در یک تاکسی بنشینند. اما لزومی ندارد که یک گروه مسافر که تازه وارد ترمینال میشود در اولین تاکسیای که جای کافی برای آنها دارد، بنشیند!
برای مثال اگر ۴ گروه تکنفره در زمانهای ۱ و ۲ و ۳ و ۴ وارد ترمینال شوند و پس از آنها دو گروه سهنفره، یکی در زمان ۱۰ و دیگری در زمان ۱۱ وارد شوند و نهایتاً دو گروه تکنفره در زمانهای ۱۰۱۰ و ۱۰۱۱ وارد ترمینال شوند، در اینصورت دو تا از روشهای ممکن عبارتند از:
برنامهای بنویسید که
برای هر سناریوی ورودی: