FastPrep
Problem · Greedy

Get Minimum Time ⏰

Learn this problem
● MediumThoughtspotOA

Problem statement

There are n services numbered from 1 to n in a system, and there are m requests to be processed. The service in which the ith request is cached is denoted by cache[i], for all 1 <= i <= m. For any request, if the request is processed from a cache, then it takes 1 unit of time. Otherwise, it takes 2 units of time.

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 the requests by allocating each request to a service.

Function

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

Complete the function getMinTime in the editor.

getMinTime has the following parameters:

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

Returns

int: the minimum time required to process all requests

Examples

Example 1

n = 3cache = [1, 1, 3, 1, 1]return = 3
If the 1st, 2nd and 4th requests are assigned to the 1st service, it will take 1 unit of time each, or 3 units of time to process them in total. Assign the 3rd request to the 2nd service and the 5th request to the 3rd service. It takes 1 and 2 units of time to complete them, respectively. Therefore, all requests are processed in 3 units of time.

Constraints

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