Job Scheduling Algorithms Implementation
Asked at:
Snowflake
Apple
Netflix
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
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.
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_idself.start_time = start_timeself.end_time = end_timeself.priority = prioritydef duration(self):return self.end_time - self.start_timedef __lt__(self, other):return self.start_time < other.start_timedef 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.
def fcfs_schedule(jobs):sorted_jobs = sorted(jobs, key=lambda j: j.start_time)schedule = []current_time = 0for 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_timereturn 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.
import heapqdef priority_schedule(jobs):sorted_jobs = sorted(jobs, key=lambda j: j.start_time)schedule = []current_time = 0ready_queue = []job_index = 0while 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 += 1if 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_timeelif job_index < len(sorted_jobs):current_time = sorted_jobs[job_index].start_timereturn 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.
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_timeturnaround = entry['finish'] - job.start_timeoutput.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
medium
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.
medium
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.
Question Timeline
See when this question was last asked and where, including any notes left by other candidates.
Mid May, 2026
Snowflake
Senior
Mid September, 2025
Netflix
Senior
Late August, 2025
Apple
Senior
Hello Interview Premium
Your account is free and you can post anonymously if you choose.