FastPrep
Problem · Array

Minimum Time to Process Requests

Learn this problem
● MediumCitadelOA

Problem statement

A system has n services numbered 1 to n, and m requests to be processed. The service where the i-th request is cached is denoted by cache[i].

Processing a request from cache takes 1 unit of time; otherwise, it takes 2 units. Different services can process different requests simultaneously, but one service can only process one request at a time.

Find the minimum time to process all requests by optimally allocating each request to a service.

Function

getMinTime(n: int, cache: int[]) → int

Complete the function getMinTime in the editor with the following parameters:

  • int n: the number of services in the system
  • int cache[m]: the service in which the request is cached

Examples

Example 1

n = 3cache = [1, 1, 3, 1, 1]return = 3

An optimal allocation:

  • Assign 1st, 2nd, and 4th requests to service 1: 3 time units.
  • Assign 3rd request to service 3: 1 time unit.
  • Assign 5th request to service 2: 2 time units.

All requests can be processed in 3 time units.

More Citadel problems

drafts saved locally
public int getMinTime(int n, int[] cache) {
  // write your code here
}
n3
cache[1, 1, 3, 1, 1]
expected3
checking account