Overview

Priority scheduling is at the heart of systems like React's Scheduler package, OS task managers, and job queues. Tasks arrive with different priority levels, and the scheduler must execute them in priority order while maintaining FIFO ordering for tasks at the same priority.

Implement createScheduler() that returns a scheduler object with two methods:

• add(taskId, priority) — enqueues a task with the given string id and numeric priority. Lower numbers = higher priority.
• run() — drains the queue and returns an array of task ids in execution order.

Constraints

• Lower numeric priority means higher urgency (0 runs before 1).
• Tasks with the same priority execute in FIFO order (insertion order).
• add can be called multiple times before run.
• run drains the entire queue — calling run again returns [].
• Unknown operations or invalid data should be silently ignored.
• Complexity target: $O(n \log n)$ where n is the number of tasks.

Examples

const scheduler = createScheduler();

scheduler.add("render", 2);
scheduler.add("urgent-update", 0);
scheduler.add("cleanup", 3);
scheduler.add("state-update", 1);

scheduler.run();
// → ["urgent-update", "state-update", "render", "cleanup"]

// FIFO within same priority.
const scheduler = createScheduler();

scheduler.add("a", 1);
scheduler.add("b", 1);
scheduler.add("c", 1);

scheduler.run();
// → ["a", "b", "c"]

// run() drains the queue.
const scheduler = createScheduler();

scheduler.add("x", 0);
scheduler.run(); // → ["x"]
scheduler.run(); // → []

Notes

• A bucketed approach works well: use a Map keyed by priority level, with each value being an array of tasks (preserves insertion order). Then sort the keys and flatten.
• Alternatively, you can use a single array and sort by (priority, insertionIndex) — this naturally gives you both priority ordering and FIFO within a bucket.
• This mirrors how React's Scheduler uses priority lanes to determine which work to flush first.

Solution

function createScheduler() {
  const buckets = new Map();

  return {
    add(taskId, priority) {
      if (!buckets.has(priority)) buckets.set(priority, []);
      buckets.get(priority).push(taskId);
    },
    run() {
      const priorities = [...buckets.keys()].sort((a, b) => a - b);
      const output = [];
      for (const p of priorities) {
        output.push(...buckets.get(p));
      }
      buckets.clear();
      return output;
    },
  };
}

Resources

• Scheduling Basics — Wikipedia
• React Scheduler Package
• Priority Queue — Wikipedia