1834. Single-Threaded CPU

At a Glance

Topic: heap-priority-queue
Pattern: Top-K / Heap (by processing time) + ordering
Difficulty: Medium
Companies: Google, Amazon, Microsoft, Meta, Apple
Frequency: Medium
LeetCode: 1834

Each task has enqueueTime, processingTime, and index. A single CPU at time T may start any available task (enqueueTime ≤ T); it picks the one with smallest processingTime, then smallest index on ties. Return the order of indices executed.

Recognition Cues

Single resource, non-preemptive scheduling with future arrivals
“Next job” among available — min-heap on (processingTime, index)
Time jumps when CPU idle and no work — advance to next enqueue

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Brute — rescan all tasks every tick — O(n^2).
Optimal — sort by enqueue, pointer + min-heap of available tasks — O(n log n).

Optimal Solution

Go

import (
	"container/heap"
	"sort"
)

type taskItem struct {
	processing int
	index      int
}

type minProcHeap []*taskItem

func (heapSlice minProcHeap) Len() int { return len(heapSlice) }
func (heapSlice minProcHeap) Less(left, right int) bool {
	if heapSlice[left].processing != heapSlice[right].processing {
		return heapSlice[left].processing < heapSlice[right].processing
	}
	return heapSlice[left].index < heapSlice[right].index
}
func (heapSlice minProcHeap) Swap(left, right int) {
	heapSlice[left], heapSlice[right] = heapSlice[right], heapSlice[left]
}

func (heapSlice *minProcHeap) Push(value any) {
	*heapSlice = append(*heapSlice, value.(*taskItem))
}

func (heapSlice *minProcHeap) Pop() any {
	old := *heapSlice
	length := len(old)
	value := old[length-1]
	*heapSlice = old[0 : length-1]
	return value
}

type indexedTask struct {
	enqueue    int
	processing int
	index      int
}

type byEnqueueTask []indexedTask

func (slice byEnqueueTask) Len() int { return len(slice) }
func (slice byEnqueueTask) Less(left, right int) bool {
	if slice[left].enqueue != slice[right].enqueue {
		return slice[left].enqueue < slice[right].enqueue
	}
	return slice[left].index < slice[right].index
}
func (slice byEnqueueTask) Swap(left, right int) {
	slice[left], slice[right] = slice[right], slice[left]
}

func getOrder(tasks [][]int) []int {
	order := make([]int, 0, len(tasks))
	sorted := make(byEnqueueTask, len(tasks))
	for position, row := range tasks {
		sorted[position] = indexedTask{
			enqueue:    row[0],
			processing: row[1],
			index:      position,
		}
	}
	sort.Sort(sorted)
	currentTime := 0
	nextIndex := 0
	available := &minProcHeap{}
	heap.Init(available)
	for nextIndex < len(sorted) || available.Len() > 0 {
		for nextIndex < len(sorted) && sorted[nextIndex].enqueue <= currentTime {
			item := sorted[nextIndex]
			heap.Push(available, &taskItem{processing: item.processing, index: item.index})
			nextIndex++
		}
		if available.Len() == 0 {
			currentTime = sorted[nextIndex].enqueue
			continue
		}
		chosen := heap.Pop(available).(*taskItem)
		order = append(order, chosen.index)
		currentTime += chosen.processing
	}
	return order
}

JavaScript

class MinHeap {
  constructor(compare) {
    this.data = [];
    this.compare = compare;
  }

  size() {
    return this.data.length;
  }

  push(item) {
    this.data.push(item);
    this.bubbleUp(this.data.length - 1);
  }

  pop() {
    if (this.data.length === 0) {
      return undefined;
    }
    const top = this.data[0];
    const last = this.data.pop();
    if (this.data.length > 0) {
      this.data[0] = last;
      this.bubbleDown(0);
    }
    return top;
  }

  bubbleUp(index) {
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      if (this.compare(this.data[index], this.data[parentIndex]) >= 0) {
        break;
      }
      this.swap(index, parentIndex);
      index = parentIndex;
    }
  }

  bubbleDown(index) {
    const length = this.data.length;
    while (true) {
      const leftChild = index * 2 + 1;
      const rightChild = index * 2 + 2;
      let smallest = index;
      if (leftChild < length && this.compare(this.data[leftChild], this.data[smallest]) < 0) {
        smallest = leftChild;
      }
      if (rightChild < length && this.compare(this.data[rightChild], this.data[smallest]) < 0) {
        smallest = rightChild;
      }
      if (smallest === index) {
        break;
      }
      this.swap(index, smallest);
      index = smallest;
    }
  }

  swap(leftIndex, rightIndex) {
    const temp = this.data[leftIndex];
    this.data[leftIndex] = this.data[rightIndex];
    this.data[rightIndex] = temp;
  }
}

function getOrder(tasks) {
  const sorted = tasks
    .map((tuple, position) => [...tuple, position])
    .sort((left, right) => {
      if (left[0] !== right[0]) {
        return left[0] - right[0];
      }
      return left[2] - right[2];
    });
  const heap = new MinHeap((left, right) => {
    if (left.processing !== right.processing) {
      return left.processing - right.processing;
    }
    return left.taskIndex - right.taskIndex;
  });
  const order = [];
  let currentTime = 0;
  let pointer = 0;
  while (pointer < sorted.length || heap.size() > 0) {
    while (pointer < sorted.length && sorted[pointer][0] <= currentTime) {
      const entry = sorted[pointer];
      heap.push({
        enqueue: entry[0],
        processing: entry[1],
        taskIndex: entry[2],
      });
      pointer += 1;
    }
    if (heap.size() === 0) {
      currentTime = sorted[pointer][0];
      continue;
    }
    const chosen = heap.pop();
    order.push(chosen.taskIndex);
    currentTime += chosen.processing;
  }
  return order;
}

Walkthrough

Tasks [enqueue, duration, index]: sort by enqueue. Push all with enqueue ≤ currentTime; pop smallest (duration,index); advance time by duration.

Invariant: Heap always matches the problem’s rule for next runnable task among those released by currentTime.

Edge Cases

CPU idle before first task — jump currentTime to first enqueue
Ties on duration — smaller index first (encoded in heap comparator)
All enqueue at 0 — pure heap order by (processing, index)

Pitfalls

Forgetting to advance currentTime when heap empty
Using FIFO instead of min-processingTime

Variants

Preemptive shortest-remaining-time — different model (not this problem)
Multiple CPUs — parallel heaps / queues

Mind-Map Tags

#heap #scheduling #simulation #time-advance #greedy