Design a walk-in service scheduler with VIP priority and a 2:1 VIP-to-regular rate

Design and implement a service scheduler for an in-person customer service center, similar to a walk-in tech support counter in a retail store. A customer who walks in checks in and receives a ticket with a sequential service number. Staff call service numbers in the order the scheduler determines. There are two tiers of customers: - **Regular** customers are served in the order they arrive. - **VIP** customers have higher priority than regular customers. The exercise was given as comments in a Java starter file, in three steps that build on each other. ### Clarifying Questions - Do VIP and regular customers share one sequence of service numbers, or does each tier have its own? - What should `getNextCustomer()` return when nobody is waiting? - Can a customer check in again while they already hold a waiting ticket? - Can more than one staff member call `getNextCustomer()` at the same time? ### Part 1 — Model the customer and the scheduler Design a `Customer` class and a `ServiceScheduler` class with the characteristics they need for this service center. ```hint What the ticket must carry Ask which data the scheduler needs to tell the tiers apart and to keep arrival order within a tier, and whether that data describes the person or one visit. ``` #### What This Part Should Cover - The fields of a customer and of a check-in, and which class owns the service number - How the tier is represented so that adding a tier later is cheap - The scheduler's public interface and what each method returns ### Part 2 — Serve every VIP first Implement `checkIn(Customer)` and `getNextCustomer()` so that all waiting VIP customers are served before any regular customer, and each tier is served in arrival order. ```hint One structure or two Compare a single priority queue ordered by tier and then by arrival with one first-in, first-out queue per tier: what each costs per call, and which one Part 3 will be easier to build on. ``` #### What This Part Should Cover - Correct ordering across tiers and within each tier - Time per call and memory, stated - Behavior on an empty scheduler and on invalid or repeated check-ins ### Part 3 — Serve VIP and regular customers at a 2:1 rate Modify `getNextCustomer()` so that VIP and regular customers are processed at a 2:1 rate. The prompt also wrote `100 : 50` next to this requirement, without further explanation. ```hint Whose turn is it Think about the smallest amount of state that tells the scheduler whose turn comes next, and what should happen to that state when one of the two queues is empty. ``` #### Clarifying Questions for this Part - Does `100 : 50` only restate the ratio, or describe a scenario such as 100 VIP and 50 regular customers waiting? - When only one tier is waiting, should the scheduler serve that tier, or hold the slot for the other tier? - Should the ratio be configurable, and does the 2:1 pattern restart after one queue empties? #### What This Part Should Cover - A deterministic interleaving that yields 2:1 while both tiers are waiting - The rule when one queue is empty, and whether the ratio state resets or carries over - Tests that pin the exact order in which customers are served ### What a Strong Answer Covers - Clear separation between the customer, the ticket for one visit, and the scheduling policy - Constant-time or logarithmic operations, with the choice of data structures justified - Explicit, tested behavior for empty queues, repeated check-ins and the ratio state - Starvation of regular customers under strict VIP priority, and the trade-off the 2:1 rate makes against it - Correctness when several staff desks call the scheduler at once ### Follow-up Questions - Several staff members at different desks call `getNextCustomer()` concurrently. How do you keep the order and the ratio correct? - The ratio must become configurable, for example 3:1. What changes, and what happens to customers already waiting? - A regular customer has waited far longer than everyone else. How would you add a maximum-wait guarantee on top of the ratio? - A customer leaves before being called. How do you remove their ticket efficiently?