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 Function Description Complete the function getMinTimein the editor.getMinTime` has the following parameters:

• int n: the number of services in the system
• int cache[m]: the service in which the request is cached Returns int: the minimum time required to process all requests

Constraints

• 1 ≤ n ≤ 10^5
• 1 ≤ m ≤ 10^5
• 1 ≤ cache[i] ≤ n

Example 1

Input:

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

Output:

3

Explanation: 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.

解法

最优策略：每个服务并行处理；同一服务上 k 个缓存请求按 1, 2, ..., k 累计，总耗时 = max over services 的 count[svc]。所以答案为某服务被分配的最大请求数；用哈希表计数即可。时间复杂度 O(m)，空间复杂度 O(min(m, n))。

from typing import List
from collections import Counter

def getMinTime(n: int, cache: List[int]) -> int:
    cnt = Counter(cache)
    return max(cnt.values()) if cnt else 0

class Solution {
    int getMinTime(int n, int[] cache) {
        Map<Integer, Integer> cnt = new HashMap<>();
        int best = 0;
        for (int c : cache) {
            int v = cnt.merge(c, 1, Integer::sum);
            best = Math.max(best, v);
        }
        return best;
    }
}

class Solution {
public:
    int getMinTime(int n, vector<int>& cache) {
        unordered_map<int, int> cnt;
        int best = 0;
        for (int c : cache) best = max(best, ++cnt[c]);
        return best;
    }
};