Game Scheduler

You are organizing a series of game rounds for a tournament, with each round represented by a team number by English alphabetical letter. However, there's a constraint: according to the game rules, rounds for the same team must be separated by at least n intervals to ensure fair gameplay which is under game rules. Your task is to determine the minimum number of intervals required to complete all the game rounds, considering the constraint on the separation of rounds for the same team.

Example 1:

Input:

["A","A","A","B","B","B"]
2

Output:

8

Explanation: A possible sequence is: A -> B -> idle -> A -> B -> idle -> A -> B.

After participate team A, you must wait two cycles before participating A again. The same applies to team B. In the 3rd interval, neither A nor B can be done, so you idle. By the 4th cycle, you can do A again as 2 intervals have passed.

Example 2:

Input:

["A","C","A","B","D","B"]
1

Output:

6

Explanation: A possible sequence is: A -> B -> C -> D -> A -> B.

With a interval of 1, you can participate a team after just one other round.

Example 3:

Input:

["A","A","A", "B","B","B"]
3

Output:

10

Explanation: A possible sequence is: A -> B -> idle -> idle -> A -> B -> idle -> idle -> A -> B.

There are only two types of teams, A and B, which need to be separated by 3 intervals. This leads to idling twice between repetitions of these team rounds.

Input Format

First-line contains an array of teams The second line contains n as the interval

Constraints

1 <= rounds.length <= 104

teams[i] is an uppercase English letter.

0 <= n <= 100

Output Format

n

Sample Input 0

["A","A","A","B","B","B"]
2

Sample Output 0

8

Sample Input 1

["A","C","A","B","D","B"]
1

Sample Output 1

6

Sample Input 2

['Y', 'K', 'F', 'H', 'K', 'W', 'W', 'C', 'H', 'N', 'A', 'B', 'P', 'B', 'B', 'G', 'X', 'Z', 'O', 'X', 'C', 'C', 'P', 'X', 'N', 'O', 'Y', 'R', 'G', 'U', 'O', 'P', 'U', 'S', 'T', 'K', 'E', 'F', 'G', 'N', 'T', 'O', 'W', 'B', 'A', 'B', 'W', 'S', 'Y', 'M', 'P', 'I', 'M', 'O', 'K', 'Z', 'G', 'H', 'U', 'I', 'I', 'M', 'X', 'Y', 'D', 'B', 'K', 'T', 'H', 'J', 'L', 'I', 'M']
96

Sample Output 2

486

Solution

By Nadeesha Jayamanne

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <queue>
#include <unordered_map>

using namespace std;
int leastIntervals(vector<char>& tasks, int interval){

    unordered_map<char, int> freq;
    for(char team: tasks){
        freq[team]++;
    }
    priority_queue<int> maxHeap;
    for(auto& pair : freq){
        maxHeap.push(pair.second);
    }
    queue<pair<int,int>> cooldown;
    int time=0;

    while(!maxHeap.empty() || !cooldown.empty()){
        time++;

        if(!maxHeap.empty()){
            int curr = maxHeap.top();
            maxHeap.pop();
            curr--;
            if(curr>0){
                cooldown.push({curr,time+interval});
            }
        }
        if(!cooldown.empty() && cooldown.front().second ==  time){
            maxHeap.push(cooldown.front().first);
            cooldown.pop();
        }
    }

    return time;
}

int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    string line;
    getline(cin, line);
    vector<char> tasks;
    for (size_t i = 0; i < line.size(); ++i) {
        if (line[i] >= 'A' && line[i] <= 'Z') {
            tasks.push_back(line[i]);
        }
    }
    int interval;
    cin>>interval;

    cout<<leastIntervals(tasks,interval);
    // for(char let:tasks){
    //     cout<<let<<endl;
    // }
    return 0;
}