⌘K

Tutor

Job Scheduling Algorithms Implementation

Asked at:

Apple

Netflix

Google

DESCRIPTION

Implement a job scheduler that supports two scheduling algorithms: First Come First Serve (FCFS) and priority-based scheduling. Each job has a start_time, end_time, and priority value. The scheduler should process jobs according to the selected algorithm and output the execution schedule with timing details. For example, given jobs with priorities [3, 1, 2] and arrival times [0, 1, 2], priority scheduling would execute the highest priority job first.

Input:

jobs = [(start=0, end=5, priority=2), (start=1, end=4, priority=1), (start=2, end=6, priority=3)]
algorithm = 'FCFS'

Output:

Job 1: 0-5
Job 2: 5-8
Job 3: 8-12

Explanation: FCFS executes jobs in arrival order. Job 1 runs 0-5, Job 2 waits until 5 and runs 5-8 (3 units), Job 3 waits until 8 and runs 8-12 (4 units).

Constraints:

Jobs have non-negative start_time, positive duration (end_time - start_time), and integer priority
FCFS schedules jobs in arrival order; Priority schedules by priority value (lower = higher priority)
Jobs cannot execute before their start_time
Handle waiting time when scheduler is idle or job hasn't arrived

Understanding the Problem

The challenge involves managing two distinct scheduling policies with different ordering rules. FCFS requires maintaining arrival order while tracking when each job becomes available. Priority scheduling needs sorting by priority among available jobs at each scheduling decision point. Both algorithms must handle waiting periods when the scheduler is idle or when the next job hasn't arrived yet, requiring careful time tracking and queue management.

Building Intuition

A naive approach might sort all jobs once at the start, but this fails because jobs have different start_time values—a job can't execute before it arrives. The key insight is to use a ready queue that only contains jobs that have arrived by the current time. For FCFS, process the ready queue in arrival order; for priority scheduling, always pick the highest priority job from the ready queue. For example, if the current time is 5 and jobs arrive at [0, 3, 7], only the first two jobs are eligible for scheduling.

Job scheduling is fundamental to operating systems (CPU scheduling), cloud computing (task allocation), and batch processing systems. Understanding FCFS helps grasp simple fairness models, while priority scheduling demonstrates how systems handle urgent tasks. These patterns apply to any resource allocation problem where requests arrive over time with different importance levels.

Common Pitfalls

Pitfall: Scheduling jobs before their start_time arrives → Fix: Check current_time >= job.start_time before adding to ready queue

Pitfall: Not advancing time when scheduler is idle → Fix: Jump current_time to next job's start_time if ready queue is empty

Pitfall: Recalculating priorities during execution → Fix: Sort/prioritize only when jobs enter the ready queue, not during execution

Implementation

Job Data Structure and Input Handling

Define a Job class to encapsulate job properties: job_id, start_time, end_time, and priority. Include a method to calculate duration (end_time - start_time) and implement comparison methods for sorting. Create a parser to convert input data into Job objects and validate constraints (non-negative times, positive duration). For example, a job with start=2, end=7, priority=1 creates a Job object with duration=5 that can be compared by arrival time or priority.

Solution

class Job:
    def __init__(self, job_id, start_time, end_time, priority):
        if start_time < 0 or end_time < 0:
            raise ValueError("Times must be non-negative")
        if end_time <= start_time:
            raise ValueError("Duration must be positive")
        self.job_id = job_id
        self.start_time = start_time
        self.end_time = end_time
        self.priority = priority
    
    def duration(self):
        return self.end_time - self.start_time
    
    def __lt__(self, other):
        return self.start_time < other.start_time
def parse_jobs(data):
    return [Job(i, d['start'], d['end'], d['priority']) for i, d in enumerate(data)]

FCFS Scheduler Implementation

Implement the First Come First Serve algorithm using the Job objects from Section 1. Sort jobs by start_time to establish arrival order, then process them sequentially. Track current_time and advance it to max(current_time, job.start_time) before executing each job to handle idle periods. Calculate finish_time = current_time + job.duration and record the schedule entry. For example, if current_time=5 and the next job starts at 8, jump to time 8 before executing.

Solution

def fcfs_schedule(jobs):
    sorted_jobs = sorted(jobs, key=lambda j: j.start_time)
    schedule = []
    current_time = 0
    
    for job in sorted_jobs:
        current_time = max(current_time, job.start_time)
        finish_time = current_time + job.duration()
        schedule.append({
            'job_id': job.job_id,
            'start': current_time,
            'finish': finish_time
        })
        current_time = finish_time
    
    return schedule

Priority-Based Scheduler Implementation

Implement priority scheduling by maintaining a ready queue (min-heap by priority) of jobs that have arrived. Iterate through jobs sorted by start_time, adding them to the ready queue when current_time >= job.start_time. At each step, pop the highest priority job from the queue, execute it, and update current_time. If the ready queue is empty but jobs remain, advance current_time to the next job's start_time. For example, at time 3 with jobs of priority [2, 1, 3] in the queue, execute the priority 1 job first.

Solution

import heapq
def priority_schedule(jobs):
    sorted_jobs = sorted(jobs, key=lambda j: j.start_time)
    schedule = []
    current_time = 0
    ready_queue = []
    job_index = 0
    
    while job_index < len(sorted_jobs) or ready_queue:
        while job_index < len(sorted_jobs) and sorted_jobs[job_index].start_time <= current_time:
            heapq.heappush(ready_queue, (sorted_jobs[job_index].priority, sorted_jobs[job_index]))
            job_index += 1
        
        if ready_queue:
            _, job = heapq.heappop(ready_queue)
            finish_time = current_time + job.duration()
            schedule.append({'job_id': job.job_id, 'start': current_time, 'finish': finish_time})
            current_time = finish_time
        elif job_index < len(sorted_jobs):
            current_time = sorted_jobs[job_index].start_time
    
    return schedule

Complete Integration and Output Formatting

Create a JobScheduler class that integrates Section 1's Job structure with Section 2's FCFS and Section 3's priority algorithms. Provide a unified interface with a schedule(jobs, algorithm) method that selects the appropriate scheduler. Format the output to display each job's execution window as Job {id}: {start}-{finish} with optional statistics like waiting time and turnaround time. For example, instantiate scheduler = JobScheduler(), call scheduler.schedule(jobs, 'FCFS'), and return a formatted schedule string showing all execution intervals.

Solution

class JobScheduler:
    def schedule(self, jobs, algorithm='FCFS'):
        if algorithm.upper() == 'FCFS':
            return self._format_schedule(fcfs_schedule(jobs))
        elif algorithm.upper() == 'PRIORITY':
            return self._format_schedule(priority_schedule(jobs))
        else:
            raise ValueError(f"Unknown algorithm: {algorithm}")
    
    def _format_schedule(self, schedule):
        output = []
        for entry in schedule:
            output.append(f"Job {entry['job_id']}: {entry['start']}-{entry['finish']}")
        return '\n'.join(output)
    
    def schedule_with_stats(self, jobs, algorithm='FCFS'):
        parsed_jobs = {job.job_id: job for job in jobs}
        schedule = fcfs_schedule(jobs) if algorithm.upper() == 'FCFS' else priority_schedule(jobs)
        output = []
        for entry in schedule:
            job = parsed_jobs[entry['job_id']]
            waiting = entry['start'] - job.start_time
            turnaround = entry['finish'] - job.start_time
            output.append(f"Job {entry['job_id']}: {entry['start']}-{entry['finish']} (Wait: {waiting}, Turnaround: {turnaround})")
        return '\n'.join(output)

What We've Learned

Pattern: Use a ready queue to manage jobs that have arrived but not yet executed, enabling dynamic scheduling decisions
Time Management: Always advance `current_time` to `max(current_time, next_job.start_time)` to handle idle periods correctly
Algorithm Selection: FCFS uses arrival order (simple queue), while priority scheduling uses a min-heap for efficient priority-based selection
Use Case: Applies to OS process scheduling, cloud task allocation, and any system where requests arrive over time with varying importance

Problems to Practice

Overview

Lesson

Intervals

Job scheduling is fundamentally an intervals problem involving start times, end times, and scheduling conflicts. This lesson provides the foundational concepts for working with time intervals that are essential for implementing scheduling algorithms.

Learn

Non-Overlapping Intervals

medium

Intervals

This problem directly relates to job scheduling by requiring selection of maximum non-overlapping intervals, which is a core scheduling optimization problem. It teaches greedy approaches similar to priority-based scheduling algorithms.

Practice

Maximum Profit in Job Scheduling

medium

Dynamic Programming

This problem is explicitly about job scheduling with start times, end times, and priorities (profits). It combines interval scheduling with optimization, making it highly relevant for understanding advanced scheduling algorithms beyond FCFS.

Practice

Question Timeline

See when this question was last asked and where, including any notes left by other candidates.

Company

Level

Region

Mid September, 2025

Netflix

Senior

Late August, 2025

Apple

Senior

Early August, 2025

Netflix

Senior

Get Premium to View All 7 Reports

Comments

Your account is free and you can post anonymously if you choose.

Hello Interview Premium

Recent interview questions

System Design Guided Practice

Exclusive content

Learn More

Job Scheduling Algorithms Implementation

DESCRIPTION

Understanding the Problem

Building Intuition

Common Pitfalls

Implementation

Job Data Structure and Input Handling

FCFS Scheduler Implementation

Priority-Based Scheduler Implementation

Complete Integration and Output Formatting

What We've Learned

Problems to Practice

Question Timeline

Comments

Questions

Learn

Links

Legal

Contact