Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Heap & Priority Queue

Task Scheduler

Medium · Heap & Priority Queue · Asked at Meta, Amazon, Microsoft, Uber

A CPU runs tasks (uppercase letters), one per time unit, or stays idle. Two runs of the same task must be at least n time units apart (n other units between them). Print the minimum number of time units to finish all tasks.

Input

First line: the tasks as a string of uppercase letters. Second line: n.

Output

The minimum number of time units.

Constraints

Formula: with f = highest frequency and c = how many tasks have it, the answer is max(total, (f − 1)(n + 1) + c). A max-heap simulation gives the same result.

Example 1

Input

AAABBB
2

Output

8

Example 2

Input

ACABDB
1

Output

6

Hints

  1. Only the counts matter. The most frequent task decides how many "frames" of length n + 1 you need.
  2. With f = the highest count and c = the number of tasks having it: answer = max(total tasks, (f − 1)·(n + 1) + c).

Approach

Lay out the most frequent task f times with n gaps after each of the first f − 1 copies: that creates (f − 1)(n + 1) slots plus a final row holding every task that also has count f (c of them). Other tasks fill the gaps. If there are more tasks than slots, no idling is needed at all and the answer is simply the number of tasks. Hence max(total, (f − 1)(n + 1) + c). A max-heap simulation produces the same number.

Complexity: O(total) time · O(26) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    string tasks;
    long long n;
    cin >> tasks >> n;
    vector<long long> cnt(26, 0);
    for (char c : tasks) cnt[c - 'A']++;
    long long f = *max_element(cnt.begin(), cnt.end());
    long long c = count(cnt.begin(), cnt.end(), f);
    cout << max((long long)tasks.size(), (f - 1) * (n + 1) + c) << "\n";
    return 0;
}

Python solution

import sys
from collections import Counter

data = sys.stdin.read().split()
tasks, n = data[0], int(data[1])
cnt = Counter(tasks)
f = max(cnt.values())
c = sum(1 for v in cnt.values() if v == f)
print(max(len(tasks), (f - 1) * (n + 1) + c))

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String tasks = sc.next();
        long n = sc.nextLong();
        long[] cnt = new long[26];
        for (char ch : tasks.toCharArray()) cnt[ch - 'A']++;
        long f = 0, c = 0;
        for (long v : cnt) f = Math.max(f, v);
        for (long v : cnt) if (v == f) c++;
        System.out.println(Math.max(tasks.length(), (f - 1) * (n + 1) + c));
    }
}

Solve Task Scheduler online · All practice problems