Task Scheduling | Queue-Based Scheduling | Queue

Overview

Task scheduling using queues is a fundamental problem in computer science where tasks, jobs, or processes need to be managed and executed in a specific order. Queues provide the perfect data structure for maintaining task order and ensuring fair processing.

Task scheduling problems often involve:

FIFO scheduling - Process tasks in arrival order
Round-robin scheduling - Cycle through tasks fairly
Priority scheduling - Process tasks by priority
Task dependencies - Handle tasks that depend on others
Resource constraints - Limited resources for task execution

Key characteristics:

Order maintenance - Queue maintains task order
Fair processing - Tasks processed in arrival order
Resource management - Manage limited resources
Dependency handling - Handle task dependencies
Efficient execution - O(1) enqueue/dequeue operations

Basic Task Scheduler

Simple FIFO task scheduler:

interface Task {
  id: number;
  name: string;
  execute: () => void;
}

class TaskScheduler {
  private queue: Task[] = [];
  private isProcessing = false;
  
  addTask(task: Task): void {
    this.queue.push(task);
    if (!this.isProcessing) {
      this.processNext();
    }
  }
  
  private async processNext(): Promise<void> {
    if (this.queue.length === 0) {
      this.isProcessing = false;
      return;
    }
    
    this.isProcessing = true;
    const task = this.queue.shift()!;
    
    try {
      task.execute();
    } catch (error) {
      console.error(`Task ${task.id} failed:`, error);
    }
    
    // Process next task
    await this.processNext();
  }
  
  getQueueSize(): number {
    return this.queue.length;
  }
  
  isEmpty(): boolean {
    return this.queue.length === 0;
  }
}

Time: O(1) enqueue, O(n) dequeue (if using shift), Space: O(n)

Key insight: Queue maintains task order for FIFO processing.

Pattern 1: Round-Robin Scheduling

Process tasks in round-robin fashion:

class RoundRobinScheduler {
  private queue: Task[] = [];
  private timeSlice: number;
  
  constructor(timeSlice: number = 100) {
    this.timeSlice = timeSlice; // milliseconds per task
  }
  
  addTask(task: Task): void {
    this.queue.push(task);
  }
  
  async schedule(): Promise<void> {
    while (this.queue.length > 0) {
      const task = this.queue.shift()!;
      
      // Execute task for time slice
      const startTime = Date.now();
      while (Date.now() - startTime < this.timeSlice && !task.isComplete()) {
        task.executeStep();
      }
      
      // If not complete, add back to queue
      if (!task.isComplete()) {
        this.queue.push(task);
      }
    }
  }
}

Time: O(n × timeSlice), Space: O(n)

Key insight: Cycle through tasks, giving each a time slice.

Pattern 2: Task Scheduling with Dependencies

Schedule tasks respecting dependencies:

function scheduleTasks(tasks: Task[], dependencies: number[][]): number[] {
  const n = tasks.length;
  const inDegree = new Array(n).fill(0);
  const graph: number[][] = new Array(n).fill(0).map(() => []);
  
  // Build graph and calculate in-degrees
  for (const [task, dep] of dependencies) {
    graph[dep].push(task);
    inDegree[task]++;
  }
  
  // Add tasks with no dependencies to queue
  const queue: number[] = [];
  for (let i = 0; i < n; i++) {
    if (inDegree[i] === 0) {
      queue.push(i);
    }
  }
  
  const result: number[] = [];
  
  while (queue.length > 0) {
    const task = queue.shift()!;
    result.push(task);
    
    // Process dependent tasks
    for (const dependent of graph[task]) {
      inDegree[dependent]--;
      if (inDegree[dependent] === 0) {
        queue.push(dependent);
      }
    }
  }
  
  // Check if all tasks scheduled (no cycles)
  return result.length === n ? result : [];
}

Time: O(V + E), Space: O(V + E)

Key insight: Use topological sort with queue for dependency resolution.

Pattern 3: Task Scheduling with Cooldown

Schedule tasks with cooldown period:

function leastInterval(tasks: string[], n: number): number {
  const freq = new Map<string, number>();
  
  // Count task frequencies
  for (const task of tasks) {
    freq.set(task, (freq.get(task) || 0) + 1);
  }
  
  const maxFreq = Math.max(...Array.from(freq.values()));
  const maxCount = Array.from(freq.values()).filter(f => f === maxFreq).length;
  
  // Calculate minimum intervals
  return Math.max(
    tasks.length,
    (maxFreq - 1) * (n + 1) + maxCount
  );
}

// Using queue for actual scheduling
class TaskSchedulerWithCooldown {
  private queue: [string, number][] = []; // [task, nextAvailableTime]
  private cooldown: number;
  private taskFreq = new Map<string, number>();
  
  constructor(cooldown: number) {
    this.cooldown = cooldown;
  }
  
  schedule(tasks: string[]): number {
    // Count frequencies
    for (const task of tasks) {
      this.taskFreq.set(task, (this.taskFreq.get(task) || 0) + 1);
    }
    
    // Sort by frequency (use priority queue in practice)
    const sortedTasks = Array.from(this.taskFreq.entries())
      .sort((a, b) => b[1] - a[1]);
    
    let time = 0;
    
    while (sortedTasks.length > 0 || this.queue.length > 0) {
      // Process tasks that are ready
      if (this.queue.length > 0 && this.queue[0][1] <= time) {
        const [task] = this.queue.shift()!;
        const freq = this.taskFreq.get(task)! - 1;
        
        if (freq > 0) {
          this.taskFreq.set(task, freq);
          this.queue.push([task, time + this.cooldown + 1]);
        }
      }
      
      // Add new task if available
      if (sortedTasks.length > 0) {
        const [task, freq] = sortedTasks.shift()!;
        this.taskFreq.set(task, freq - 1);
        
        if (freq > 1) {
          this.queue.push([task, time + this.cooldown + 1]);
        }
      }
      
      time++;
    }
    
    return time;
  }
}

Time: O(n), Space: O(n)

Key insight: Track next available time for each task.

Pattern 4: CPU Task Scheduler

Simulate CPU task scheduling:

interface CPUTask {
  id: number;
  arrivalTime: number;
  burstTime: number;
  priority?: number;
}

class CPUScheduler {
  private readyQueue: CPUTask[] = [];
  private currentTime = 0;
  
  addTask(task: CPUTask): void {
    this.readyQueue.push(task);
    // Sort by priority or arrival time
    this.readyQueue.sort((a, b) => 
      (a.priority || 0) - (b.priority || 0) || 
      a.arrivalTime - b.arrivalTime
    );
  }
  
  schedule(): CPUTask[] {
    const completed: CPUTask[] = [];
    
    while (this.readyQueue.length > 0) {
      const task = this.readyQueue.shift()!;
      
      // Wait if task hasn't arrived
      if (this.currentTime < task.arrivalTime) {
        this.currentTime = task.arrivalTime;
      }
      
      // Execute task
      this.currentTime += task.burstTime;
      completed.push(task);
    }
    
    return completed;
  }
  
  getCurrentTime(): number {
    return this.currentTime;
  }
}

Time: O(n log n) for sorting, Space: O(n)

Key insight: Maintain ready queue sorted by priority/arrival time.

Pattern 5: Parallel Task Scheduling

Schedule tasks on multiple processors:

class ParallelTaskScheduler {
  private queues: Task[][] = [];
  private numProcessors: number;
  
  constructor(numProcessors: number) {
    this.numProcessors = numProcessors;
    this.queues = new Array(numProcessors).fill(0).map(() => []);
  }
  
  addTask(task: Task, processorId?: number): void {
    if (processorId !== undefined) {
      this.queues[processorId].push(task);
    } else {
      // Add to shortest queue (load balancing)
      const shortestQueue = this.queues.reduce((min, q, i) => 
        q.length < this.queues[min].length ? i : min, 0
      );
      this.queues[shortestQueue].push(task);
    }
  }
  
  async schedule(): Promise<void> {
    const processors = this.queues.map((queue, id) => 
      this.processQueue(queue, id)
    );
    
    await Promise.all(processors);
  }
  
  private async processQueue(queue: Task[], processorId: number): Promise<void> {
    while (queue.length > 0) {
      const task = queue.shift()!;
      await task.execute();
    }
  }
}

Time: O(n / processors), Space: O(n)

Key insight: Distribute tasks across multiple queues for parallel processing.

Pattern 6: LeetCode - Task Scheduler

LeetCode problem: schedule tasks with cooldown:

function leastInterval(tasks: string[], n: number): number {
  const freq = new Map<string, number>();
  
  // Count frequencies
  for (const task of tasks) {
    freq.set(task, (freq.get(task) || 0) + 1);
  }
  
  // Find max frequency
  const frequencies = Array.from(freq.values());
  const maxFreq = Math.max(...frequencies);
  const maxCount = frequencies.filter(f => f === maxFreq).length;
  
  // Calculate minimum time
  return Math.max(
    tasks.length,
    (maxFreq - 1) * (n + 1) + maxCount
  );
}

Time: O(n), Space: O(1)

Key insight: Most frequent task determines minimum time.

Pattern 7: Job Queue with Retry

Task scheduler with retry mechanism:

interface Job {
  id: number;
  execute: () => Promise<void>;
  maxRetries: number;
  retryCount: number;
}

class JobQueueWithRetry {
  private queue: Job[] = [];
  private failedQueue: Job[] = [];
  
  addJob(job: Job): void {
    this.queue.push(job);
  }
  
  async processJobs(): Promise<void> {
    while (this.queue.length > 0) {
      const job = this.queue.shift()!;
      
      try {
        await job.execute();
      } catch (error) {
        job.retryCount++;
        
        if (job.retryCount < job.maxRetries) {
          // Retry: add back to queue
          this.queue.push(job);
        } else {
          // Max retries reached: move to failed queue
          this.failedQueue.push(job);
        }
      }
    }
  }
  
  getFailedJobs(): Job[] {
    return this.failedQueue;
  }
}

Time: O(n × retries), Space: O(n)

Key insight: Retry failed tasks up to max retries.

When to Use Task Scheduling with Queues

Use queue-based task scheduling when you see:

"Schedule tasks" - Need to manage task execution order
"Round-robin" - Fair task distribution
"FIFO processing" - Process tasks in arrival order
"Task queue" - Maintain queue of pending tasks
"Job scheduling" - Schedule jobs with dependencies
"Resource management" - Manage limited resources
"Cooldown" - Tasks with cooldown periods

Key distinction:

Queue-based scheduling - FIFO order, simple and fair
Priority queue scheduling - Priority-based order
Round-robin - Fair time-sliced scheduling

Task Scheduling Patterns

| Pattern | Description | Use Case |

|---------|-------------|----------|

| FIFO | First in, first out | Simple task processing |

| Round-Robin | Cycle through tasks | Fair CPU scheduling |

| Priority | Process by priority | Important tasks first |

| Dependencies | Respect task dependencies | Build systems, workflows |

| Cooldown | Enforce cooldown periods | Rate limiting, API calls |

| Parallel | Multiple processors | Distributed systems |

Remember:

Queue for FIFO task scheduling
Priority queue for priority-based scheduling
Round-robin for fair time-sliced scheduling

Template (Basic Task Scheduler)

class TaskSchedulerTemplate<T> {
  private queue: T[] = [];
  
  addTask(task: T): void {
    this.queue.push(task);
  }
  
  processNext(): T | undefined {
    return this.queue.shift();
  }
  
  processAll(): T[] {
    const result: T[] = [];
    while (this.queue.length > 0) {
      result.push(this.queue.shift()!);
    }
    return result;
  }
  
  isEmpty(): boolean {
    return this.queue.length === 0;
  }
  
  size(): number {
    return this.queue.length;
  }
}

Template (Round-Robin Scheduler)

class RoundRobinTemplate<T> {
  private queue: T[] = [];
  private timeSlice: number;
  
  constructor(timeSlice: number) {
    this.timeSlice = timeSlice;
  }
  
  addTask(task: T): void {
    this.queue.push(task);
  }
  
  schedule(): void {
    while (this.queue.length > 0) {
      const task = this.queue.shift()!;
      
      // Process task for time slice
      // processTask(task, this.timeSlice);
      
      // If not complete, add back
      // if (!task.isComplete()) {
      //   this.queue.push(task);
      // }
    }
  }
}

Time and Space Complexity

Basic Task Scheduler

addTask: O(1)
processNext: O(1) with linked list, O(n) with array shift
processAll: O(n)
Space: O(n)

Round-Robin Scheduler

addTask: O(1)
schedule: O(n × timeSlice)
Space: O(n)

Task Scheduling with Dependencies

Time: O(V + E) where V is tasks, E is dependencies
Space: O(V + E)

Practice Tips

Choose right structure - Queue for FIFO, priority queue for priority
Handle dependencies - Use topological sort for dependencies
Time management - Track current time for scheduling
Resource constraints - Limit concurrent tasks
Error handling - Handle task failures gracefully
Retry logic - Implement retry for failed tasks
Load balancing - Distribute tasks across processors

Common Mistakes

Using shift() - O(n) operation, use linked list instead
Not handling dependencies - Forgetting to check dependencies
Race conditions - Not handling concurrent access
Infinite loops - Circular dependencies in task graph
Resource exhaustion - Not limiting concurrent tasks
Time tracking - Not tracking time correctly
Priority confusion - Wrong priority ordering

Real-World Applications

Task scheduling with queues is used extensively in:

Operating Systems - Process scheduling, CPU scheduling
Web Servers - Request handling, connection pools
Database Systems - Transaction scheduling
Distributed Systems - Job queues, task distribution
Build Systems - Dependency resolution, parallel builds
CI/CD Pipelines - Job scheduling, workflow management
Message Queues - RabbitMQ, Kafka, AWS SQS
Game Engines - Task scheduling, AI decision making

Related Concepts

Queue - Data structure for task scheduling
Priority Queue - Priority-based task scheduling
Topological Sort - Dependency resolution
Round-Robin - Fair scheduling algorithm
Load Balancing - Distributing tasks

Summary

Task scheduling using queues is fundamental for:

Order maintenance - Queue maintains task order
Fair processing - FIFO ensures fair task processing
Resource management - Manage limited resources
Dependency handling - Handle task dependencies
Efficient execution - O(1) operations for task management

Key takeaways:

Use queue for FIFO task scheduling
Handle dependencies with topological sort
Implement round-robin for fair scheduling
Track time for time-based scheduling
Essential for operating systems and distributed systems

Mastering task scheduling with queues will help you solve scheduling problems, manage resources efficiently, and design robust systems in coding interviews.