Task Scheduler
You are given an array of CPU tasks, each represented by letters A to Z, and a cooling time, n. Each cycle or interval allows the completion of one task. Tasks can be completed in any order, but there's a constraint: identical tasks must be separated by at least n intervals due to cooling time.
Return the minimum number of intervals required to complete all tasks.
public int leastInterval(char[] tasks, int n) {
Map<Character, Integer> map = new HashMap<>();
for (int i = 0; i < tasks.length; i++) {
map.put(tasks[i], map.getOrDefault(tasks[i], 0) + 1); // map key is TaskName, and value is number of times to be executed.
}
PriorityQueue<Map.Entry<Character, Integer>> q = new PriorityQueue<>( //frequency sort
(a,b) -> a.getValue() != b.getValue() ? b.getValue() - a.getValue() : a.getKey() - b.getKey());
q.addAll(map.entrySet());
int count = 0;
while (!q.isEmpty()) {
int k = n + 1;
List<Map.Entry> tempList = new ArrayList<>();
while (k > 0 && !q.isEmpty()) {
Map.Entry<Character, Integer> top = q.poll(); // most frequency task
top.setValue(top.getValue() - 1); // decrease frequency, meaning it got executed
tempList.add(top); // collect task to add back to queue
k--;
count++; //successfully executed task
}
for (Map.Entry<Character, Integer> e : tempList) {
if (e.getValue() > 0) q.add(e); // add valid tasks
}
if (q.isEmpty()) break;
count = count + k; // if k > 0, then it means we need to be idle
}
return count;
}Related Problems
You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.
Return true if you can reach the last index, or false otherwise.
Given an array nums with n integers, your task is to check if it could become non-decreasing by modifying at most one element.
We define an array is non-decreasing if nums[i] <= nums[i + 1] holds for every i (0-based) such that (0 <= i <= n - 2).
You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].
Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where:
0 <= j <= nums[i] and
i + j < n
Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].
You are given an integer array prices where prices[i] is the price of a given stock on the ith day.
On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.
Find and return the maximum profit you can achieve.