educative.io

Simplify scheduling tasks solution

Courses
,
#1 
function schedule_tasks(tasks,k){
const config = {};

tasks.forEach((task)=>{
    config[task] = config[task] || 0;
    config[task]++;
});

const maxHeap = new Heap([], null, ((a, b) => a[0] - b[0]));

Object.keys(config).forEach((task)=>{
    maxHeap.push([config[task], task]);
})

const [max, task] = maxHeap.pop();

let intervalCount = (max - 1)*( k + 1 ) + 1;

while(maxHeap.length){
    const [num, key] = maxHeap.pop();
    if(num == max){
        intervalCount++;
    } 
}

return intervalCount;

}

Type your question above this line.

Course: https://www.educative.io/collection/5668639101419520/5671464854355968
Lesson: https://www.educative.io/collection/page/5668639101419520/5671464854355968/6209895416201216

#2

Hi Nicole! I had the same approach, taking the highest frequency (minus one) and multiplying by k (plus one, and then all plus one). This gives the frame where the rest of the tasks can be fitted. But the space to be fitted is limited, so your solution doesn’t work when not all tasks weight the same and the lighter ones cannot be fitted already, like:

schedule_tasks(['a', 'a', 'b', 'b', 'c', 'd'], 2): Answers 5 instead of 6
schedule_tasks(['a', 'a', 'b', 'b', 'c', 'c', 'd'], 2): Answers 6 instead of 7

Also, the problem doesn’t ask for the list of tasks in the result, so there is no point in saving the names in the heap. My solution:

def schedule_tasks(tasks, k):
  freqs = {}
  for c in tasks:
    freqs[c] = freqs.get(c, 0) + 1

  max_freqs = []
  for c in freqs:
    heappush(max_freqs, -freqs[c])

  most_frequent = -heappop(max_freqs)
  result = (most_frequent - 1) * (k + 1) + 1
  available = result - most_frequent
  while max_freqs:
    freq = -heappop(max_freqs)
    if freq == most_frequent:
      result += 1
      freq -= 1
    if freq < available:
      available -= freq
    else:
      result += freq - available
      available = 0
  return result