I solve a puzzle for a queue from an arbitrary number of customers at *n* cash registers in the supermarket, where the queue is specified by an array of integers, each of which means the time of service for the corresponding buyer at the cash register.

There was a problem in the most difficult case, when the number of cash desks is more than one ( n > 1 ) and the number of customers in the queue is greater than the number of cash desks ( customers.length > n ).

 import java.util.Arrays; public class Solution { public static int solveSuperMarketQueue(int[] customers, int n) { int sum = 0; int[] nCustomers; int[] restOfCustomers; if (customers.length == 0) { return 0; } else if (customers.length == 1) { return customers[0]; } else { if (n == 0) { return 0; } else if (n == 1) { sum = sumOfArray(customers); } else if (customers.length <= n) { int customerMax = customers[0]; for (int i = 0; i < n; i++) { if (customers[i] > customerMax) { customerMax = customers[i]; } } return customerMax; } else { nCustomers = Arrays.copyOfRange(customers, 0, n); restOfCustomers = Arrays.copyOfRange(customers, n, customers.length); int serviceTime = 0; while (sumOfArray(nCustomers) > 0) { for (int i = 0; i < nCustomers.length; i++) { nCustomers[i]--; if (nCustomers[i] == 0) { nCustomers[i] = restOfCustomers[0]; restOfCustomers = Arrays.copyOfRange(restOfCustomers, 1, restOfCustomers.length); } serviceTime++; } return serviceTime; } } } return sum; } public static int sumOfArray(int ary[]) { int s = 0; for (int i = 0; i < ary.length; i++) { s += ary[i]; } return s; } }

Namely this fragment:

 } else { nCustomers = Arrays.copyOfRange(customers, 0, n); restOfCustomers = Arrays.copyOfRange(customers, n, customers.length); int serviceTime = 0; while (sumOfArray(nCustomers) > 0) { for (int i = 0; i < nCustomers.length; i++) { nCustomers[i]--; if (nCustomers[i] == 0) { nCustomers[i] = restOfCustomers[0]; restOfCustomers = Arrays.copyOfRange(restOfCustomers, 1, restOfCustomers.length); } serviceTime++; } return serviceTime; }

Here I broke an array of customers from the condition of customers into two subarrays - nCustomers (these are the first n buyers that approached n cash registers) and restOfCustomers (this is the remaining queue).

My reasoning is this: as long as someone has a cash register, we start the serviceTime service time counter, decreasing each element of the nCustomers array for each iteration.

After each iteration, we check to see if any element in this array has zeroed, and if it is zeroed, we assign the first element from the subarray of the remaining restOfCustomers queue to restOfCustomers , and shorten this subarray itself to this element passed to nCustomers .

Tell me - was I mistaken in the logic of the decision, or was the logic correct, and was the implementation in the code incorrect?

  • indent the order, the error will be more noticeable. And when the queue ends, your program crashes. - zRrr

1 answer 1

  • sumOfArray (nCustomers) and nCustomers [i] -; - The decrement of customer service time may be negative, when service has already been completed at any box office and there are no new customers.

  • if (nCustomers [i] == 0) - in this if we, again, get into when the service is not completed at any of the cash registers, and the queue is already empty, i.e. restOfCustomers.length == 0 / Respectively - going beyond the array boundary. Corrected inaccuracies in the code, it seems, considers. The corrected version of solveSuperMarketQueue:

    public static int solveSuperMarketQueue (int [] customers, int n) {

     int sum = 0; int[] nCustomers; int[] restOfCustomers; if (customers.length == 0) { return 0; } else if (customers.length == 1) { return customers[0]; } else { if (n == 0) { return 0; } else if (n == 1) { sum = sumOfArray(customers); return sum; } else if (customers.length <= n) { int customerMax = customers[0]; for (int i = 0; i < n; i++) { if (customers[i] > customerMax) { customerMax = customers[i]; } } return customerMax; } else { nCustomers = Arrays.copyOfRange(customers, 0, n); // раскидал ΠΏΠΎ n кассам n ΠΏΠΎΠΊΡƒΠΏΠ°Ρ‚Π΅Π»Π΅ΠΉ restOfCustomers = Arrays.copyOfRange(customers, n, customers.length); // сохранил ΠΎΡΡ‚Π°Π²ΡˆΡƒΡŽΡΡ ΠΎΡ‡Π΅Ρ€Π΅Π΄ΡŒ int serviceTime = 0; // врСмя обслуТивания while (sumOfArray(nCustomers) > 0) { // Ρ†ΠΈΠΊΠ» ΠΏΠΎΠΊΠ° кассы ΠΎΠ±ΡΠ»ΡƒΠΆΠΈΠ²Π°ΡŽΡ‚ ΠΎΡ‡Π΅Ρ€Π΅Π΄ΡŒ serviceTime++; // ΡƒΡ‡Π»ΠΈ ΠΌΠΈΠ½ΡƒΡ‚Ρƒ обслуТивания for (int i = 0; i < nCustomers.length; i++) { // Ρ†ΠΈΠΊΠ» ΠΏΠ΅Ρ€Π΅Π±ΠΎΡ€Π° касс if (nCustomers[i] > 0) { nCustomers[i]--; } // ΠΌΠΈΠ½ΡƒΡ‚Π° Ρ€Π°Π±ΠΎΡ‚Ρ‹ кассы if (nCustomers[i] == 0 && restOfCustomers.length > 0) { // Ссли касса обслуТила ΠΊΠ»ΠΈΠ΅Π½Ρ‚Π° nCustomers[i] = restOfCustomers[0]; // взяли Π½Π° обслуТиваниС ΡΠ»Π΅Π΄ΡƒΡŽΡ‰Π΅Π³ΠΎ restOfCustomers = Arrays.copyOfRange(restOfCustomers, 1, restOfCustomers.length); // ΡƒΠ±Ρ€Π°Π»ΠΈ ΠΈΠ· ΠΎΡ‡Π΅Ρ€Π΅Π΄ΠΈ обслуТиваСмого ΠΊΠ»ΠΈΠ΅Π½Ρ‚Π° } } } return serviceTime; } }

    }