Design a cron job scheduler, similar to Airflow, that creates scheduled job occurrences and assigns them to available workers.

The scheduler must support one-time and recurring jobs, multiple workers, failed-attempt retries, duplicate-dispatch prevention, and execution-status monitoring.

Time is represented by nonnegative integer seconds. A cron schedule is represented by its first execution time and a fixed interval between later executions.

Class

CronJobScheduler

Constructor

public CronJobScheduler()

• Initializes an empty scheduler with no jobs or workers.
• The scheduler's initial current time is 0 seconds.

Methods

registerWorker

public boolean registerWorker(String workerId)

• Registers a worker that can execute job attempts.
• A newly registered worker is initially available.
• Returns true when the worker is registered successfully.
• Returns false when workerId is blank or already registered.
• A rejected call does not change the registered workers.
• Worker registration is not time-dependent, so this method does not receive or change currentTimeInSeconds.

scheduleJob

public boolean scheduleJob( String jobId, long firstRunTimeInSeconds, long intervalInSeconds, int maxRetries, long currentTimeInSeconds)

• Creates a new scheduled job identified by jobId.
• The first occurrence is scheduled for firstRunTimeInSeconds.
• When intervalInSeconds is 0, the job has exactly one occurrence.
• When intervalInSeconds is positive, later occurrences are scheduled every intervalInSeconds seconds.
• maxRetries is the maximum number of additional attempts allowed after the first attempt fails.
• currentTimeInSeconds is the time at which the scheduling request is made.
• Returns true when the job is scheduled successfully.
• Returns false when jobId is blank, the job ID already exists, or firstRunTimeInSeconds is earlier than currentTimeInSeconds.
• A rejected call does not create or modify a job.

dispatchJobs

public List<String> dispatchJobs( long currentTimeInSeconds)

• Processes all job occurrences scheduled at or before currentTimeInSeconds.
• Creates every due occurrence that has not already been created.
• Assigns pending occurrences to currently available workers.
• Returns one string for each newly assigned attempt in the format "jobId,scheduledTimeInSeconds,attemptNumber,workerId".
• Attempt numbers begin at 1 and increase by one after each failed attempt that is eligible for a retry.
• The maximum attempt number for an occurrence is maxRetries + 1.
• Pending occurrences are considered by scheduled time in ascending order and then by job ID in lexicographically ascending order.
• Available workers are assigned in lexicographically ascending workerId order.
• Returned assignment strings follow the order in which assignments are made.
• When no worker is available, an occurrence waiting for its first attempt remains QUEUED, and an occurrence waiting for a retry remains RETRY_PENDING.
• A dispatched worker remains busy until its attempt is completed.
• Calling this method repeatedly for the same currentTimeInSeconds does not create or dispatch a duplicate occurrence.
• Returns an empty list when no pending occurrence can be assigned.

completeJob

public boolean completeJob( String jobId, long scheduledTimeInSeconds, int attemptNumber, boolean successful, long currentTimeInSeconds)

• Reports the result of a particular attempt for the occurrence identified by jobId and scheduledTimeInSeconds.
• attemptNumber identifies the attempt whose result is being reported.
• The supplied attemptNumber must equal the number of the occurrence's currently running attempt.
• currentTimeInSeconds is the time at which the worker reports the attempt's result.
• When the completion is accepted, the worker executing that attempt becomes available.
• When successful is true, the occurrence becomes SUCCEEDED and is never dispatched again.
• When successful is false and another retry is allowed, the occurrence becomes RETRY_PENDING.
• A retry can be dispatched by the next dispatchJobs call, including another call with the same currentTimeInSeconds.
• When successful is false and no retry remains, the occurrence becomes FAILED.
• Returns true when the completion report is accepted because the specified attempt is currently running.
• The returned boolean indicates whether the completion report was accepted, not whether the attempt succeeded.
• Returns false when the specified occurrence does not currently have a running attempt or attemptNumber is not the number of its currently running attempt.
• A delayed or duplicate completion report for an earlier attempt cannot complete or otherwise modify a later attempt.
• An unsuccessful call does not modify any occurrence or worker, but its currentTimeInSeconds still becomes the scheduler's current time.

getJobStatus

public String getJobStatus( String jobId, long scheduledTimeInSeconds, long currentTimeInSeconds)

• Returns the current status of the occurrence identified by jobId and scheduledTimeInSeconds.
• currentTimeInSeconds is the time at which the status is requested.
• Returns "SCHEDULED" when the specified time belongs to the job's schedule but the occurrence has not yet been created by dispatchJobs.
• Returns "QUEUED" when the occurrence is waiting for its first attempt.
• Returns "RETRY_PENDING" when a failed occurrence is waiting for another attempt.
• Returns "RUNNING", "SUCCEEDED", or "FAILED" when the occurrence is in that state.
• Returns an empty string "" when the job does not exist or scheduledTimeInSeconds is not one of its scheduled occurrence times.
• Requesting a status does not automatically create or dispatch a due occurrence.

Time Rules

• Every method that receives currentTimeInSeconds first advances the scheduler's current time to that value.
• Across all methods on the same scheduler instance, supplied currentTimeInSeconds values are monotonically nondecreasing.
• Multiple method calls may use the same currentTimeInSeconds.
• A method call updates the scheduler's current time even when its requested operation is rejected or produces an empty result.
• Only dispatchJobs creates due occurrences and assigns them to workers.
• registerWorker has no time-dependent behavior and does not change the scheduler's current time.

Scheduling Rules

• A one-time job has exactly one occurrence at firstRunTimeInSeconds.
• A recurring job has occurrences at firstRunTimeInSeconds + k * intervalInSeconds for every integer k ≥ 0.
• Each occurrence is uniquely identified by its jobId and scheduledTimeInSeconds.
• Attempt numbers are unique within an occurrence, start at 1, and are never reused.
• The maximum attempt number for an occurrence is maxRetries + 1.
• Different occurrences of the same recurring job may run concurrently on different workers.
• A worker can execute at most one attempt at a time.
• An occurrence can have at most one running attempt at a time.
• Queued first attempts and pending retries participate in the same deterministic dispatch order.
• If two pending occurrences have the same scheduled time, the lexicographically smaller job ID is dispatched first.
• All lexicographical comparisons use the natural case-sensitive order of Java String.compareTo.
• Job IDs and worker IDs are stored exactly as supplied and are not trimmed.
• A string is blank when it is empty or contains only whitespace characters.
• The scheduler does not execute job code. It only controls occurrence creation, assignment, retry, and status.
• Persistent storage, networking, leader election, clock synchronization, and actual worker processes are outside the scope of this problem.

Constraints

• All public method calls are processed sequentially. Concurrent method invocations and thread safety are outside the scope of this problem.
• 1 ≤ workerId.length() ≤ 100
• 1 ≤ jobId.length() ≤ 100
• Worker IDs and job IDs do not contain the comma character ','.
• At most 1,000 workers are registered.
• At most 100,000 jobs are scheduled.
• 0 ≤ firstRunTimeInSeconds ≤ 1,000,000,000,000
• 0 ≤ intervalInSeconds ≤ 1,000,000,000
• 0 ≤ scheduledTimeInSeconds ≤ 1,000,000,000,000
• 0 ≤ currentTimeInSeconds ≤ 1,000,000,000,000
• 0 ≤ maxRetries ≤ 10
• 1 ≤ attemptNumber ≤ 11
• Across all applicable method calls on one scheduler instance, currentTimeInSeconds values are monotonically nondecreasing.
• A valid scheduleJob call satisfies firstRunTimeInSeconds ≥ currentTimeInSeconds.
• Across all calls, at most 200,000 occurrences become due.
• The total number of constructor and method calls does not exceed 100,000.
• No parameter is null.

Examples

Example 1: Recurring Job and Worker Ordering

CronJobScheduler scheduler = new CronJobScheduler()

scheduler.registerWorker( workerId = "worker-b") returns true.

scheduler.registerWorker( workerId = "worker-a") returns true.

scheduler.scheduleJob( jobId = "inventory-sync", firstRunTimeInSeconds = 10, intervalInSeconds = 5, maxRetries = 1, currentTimeInSeconds = 0) returns true.

scheduler.dispatchJobs( currentTimeInSeconds = 9) returns [] because the first occurrence is not yet due.

scheduler.getJobStatus( jobId = "inventory-sync", scheduledTimeInSeconds = 10, currentTimeInSeconds = 9) returns "SCHEDULED".

scheduler.dispatchJobs( currentTimeInSeconds = 10) returns ["inventory-sync,10,1,worker-a"]. Both workers are available, so the lexicographically smaller worker is selected.

scheduler.completeJob( jobId = "inventory-sync", scheduledTimeInSeconds = 10, attemptNumber = 1, successful = true, currentTimeInSeconds = 11) returns true.

scheduler.getJobStatus( jobId = "inventory-sync", scheduledTimeInSeconds = 10, currentTimeInSeconds = 11) returns "SUCCEEDED".

scheduler.dispatchJobs( currentTimeInSeconds = 15) returns ["inventory-sync,15,1,worker-a"] for the next recurring occurrence.

Example 2: Retry and Attempt Identification

CronJobScheduler scheduler = new CronJobScheduler()

scheduler.registerWorker( workerId = "worker-7") returns true.

scheduler.scheduleJob( jobId = "daily-report", firstRunTimeInSeconds = 20, intervalInSeconds = 0, maxRetries = 1, currentTimeInSeconds = 0) returns true.

scheduler.dispatchJobs( currentTimeInSeconds = 20) returns ["daily-report,20,1,worker-7"].

scheduler.completeJob( jobId = "daily-report", scheduledTimeInSeconds = 20, attemptNumber = 1, successful = false, currentTimeInSeconds = 21) returns true.

scheduler.getJobStatus( jobId = "daily-report", scheduledTimeInSeconds = 20, currentTimeInSeconds = 21) returns "RETRY_PENDING".

scheduler.dispatchJobs( currentTimeInSeconds = 21) returns ["daily-report,20,2,worker-7"].

scheduler.completeJob( jobId = "daily-report", scheduledTimeInSeconds = 20, attemptNumber = 1, successful = true, currentTimeInSeconds = 22) returns false because attempt 2, not attempt 1, is currently running.

scheduler.getJobStatus( jobId = "daily-report", scheduledTimeInSeconds = 20, currentTimeInSeconds = 22) returns "RUNNING" because the rejected completion report did not modify attempt 2.

scheduler.completeJob( jobId = "daily-report", scheduledTimeInSeconds = 20, attemptNumber = 2, successful = false, currentTimeInSeconds = 23) returns true.

scheduler.getJobStatus( jobId = "daily-report", scheduledTimeInSeconds = 20, currentTimeInSeconds = 23) returns "FAILED" because the initial attempt and the single allowed retry both failed.

Example 3: Deterministic Dispatch and Duplicate Prevention

CronJobScheduler scheduler = new CronJobScheduler()

scheduler.registerWorker( workerId = "worker-z") returns true.

scheduler.registerWorker( workerId = "worker-a") returns true.

scheduler.scheduleJob( jobId = "beta", firstRunTimeInSeconds = 30, intervalInSeconds = 0, maxRetries = 0, currentTimeInSeconds = 0) returns true.

scheduler.scheduleJob( jobId = "alpha", firstRunTimeInSeconds = 30, intervalInSeconds = 0, maxRetries = 0, currentTimeInSeconds = 0) returns true.

scheduler.dispatchJobs( currentTimeInSeconds = 30) returns ["alpha,30,1,worker-a", "beta,30,1,worker-z"]. Job IDs and worker IDs are both processed in lexicographically ascending order.

scheduler.dispatchJobs( currentTimeInSeconds = 30) returns [] because both occurrences are already running and cannot be dispatched twice.