Task Scheduler
Medium Problems DSA practice problem on Onlearn.
Difficulty: medium.
Topics: What is Binary Search and how can it be implemented to efficiently locate an element in a sorted array?, Frequency Counting, Greedy Algorithm, Heap/Priority Queue, Mathematical Algorithms, Sorting, space complexity, array, divide and conquer, iterative vs recursive, binary search, time complexity analysis.
Problem Statement You are given an array of CPU tasks, where each task is represented by an uppercase English letter (e.g., 'A', 'B', 'C'). You are also given a non negative integer n representing the cooling period. The CPU processes these tasks in a specific order. Each unit of time represents one cycle, during which the CPU can either complete one task or stay idle. The constraint is that identical tasks must be separated by at least n units of time (intervals) due to the cooling period. Your objective is to determine the minimum number of units of time required to complete all the given tasks. Input Specification The first line contains an array of characters representing the tasks. The second line contains a non negative integer n . Output Specification A single integer representing the minimum total intervals required to finish all tasks. Constraints 1 ≤ Number of tasks ≤ 10^4 Tasks consist of uppercase English letters ('A' 'Z'). 0 ≤ n ≤ 100 Sample Test Cases Sample Input 1 Sample Output 1 Explanation: A possible sequence is: A B idle A B idle A B. There are at least 2 units of time between any two identical tasks. Total time = 8 units. Sample Input 2 Sample Output 2 Explanation: Since the cooling period is 0, the CPU can process tasks continuously without any idle time. One possible order is A A A B B B. Total time = 6 units. Sample Input 3 Sample Output 3 Explanation: The task 'A' has the highest frequency (6). One possible sequence is: A B C A D E A F G A idle idle A idle idle A Total time = 16 units. Difficulty Level Medium