Schedule Fixed-Order Tasks with a Cooldown

Quick Overview

Find the minimum calendar days needed to execute tasks in their fixed input order when repeated task IDs require a specified number of complete cooldown days between executions.

Schedule Fixed-Order Tasks with a Cooldown

Company: Coinbase

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

## Problem Tasks must execute in the given order. Each task has a string ID, and at most one task can execute per day. Between two executions of the same ID, at least `cooldown` complete days must pass. Idle days may be inserted. Return the minimum number of calendar days needed to execute every task without reordering them. For example, with cooldown `2`, executions of the same ID on days `1` and `4` are valid because days `2` and `3` lie between them. ### Function Contract Implement `minimumFixedOrderScheduleDays(tasks, cooldown)`. ### Constraints & Assumptions - `0 <= len(tasks) <= 200,000`. - Task IDs are nonempty ASCII strings. - `0 <= cooldown <= 10^9`. - Day numbering starts at `1`; an empty task list takes `0` days. - The answer may exceed signed 32-bit range. ### Clarifying Questions to Ask - May tasks be reordered? No. - Does cooldown zero allow identical tasks on consecutive days? Yes. - Are idle days counted in the answer? Yes. ```hint Track the last scheduled day For the next task, its day is the larger of the next free day and `lastDay[task] + cooldown + 1`. ``` ### Examples ```text tasks = ["A","A"], cooldown = 2 -> 4 tasks = ["A","B","A"], cooldown = 2 -> 4 tasks = ["A","A","A"], cooldown = 0 -> 3 tasks = [], cooldown = 5 -> 0 ``` ### Evaluation Focus - Preserves fixed task order. - Interprets the number of complete intervening days correctly through `cooldown + 1`. - Handles zero cooldown, empty input, arbitrary string IDs, and large answers. - Runs in `O(n)` expected time with a hash map. ### Extensions to Discuss 1. How does the problem change if tasks may be reordered? 2. How would per-task cooldown values alter the state? 3. How could actual timestamps replace integer days?

Quick Answer: Find the minimum calendar days needed to execute tasks in their fixed input order when repeated task IDs require a specified number of complete cooldown days between executions.

|Home/Coding & Algorithms/Coinbase
Coinbase logo
Coinbase
May 12, 2026, 12:00 AM
mediumSoftware EngineerOnsiteCoding & Algorithms
1
0

Problem

Tasks must execute in the given order. Each task has a string ID, and at most one task can execute per day. Between two executions of the same ID, at least cooldown complete days must pass. Idle days may be inserted.

Return the minimum number of calendar days needed to execute every task without reordering them.

For example, with cooldown 2, executions of the same ID on days 1 and 4 are valid because days 2 and 3 lie between them.

Function Contract

Implement minimumFixedOrderScheduleDays(tasks, cooldown).

Constraints & Assumptions

  • 0 <= len(tasks) <= 200,000 .
  • Task IDs are nonempty ASCII strings.
  • 0 <= cooldown <= 10^9 .
  • Day numbering starts at 1 ; an empty task list takes 0 days.
  • The answer may exceed signed 32-bit range.

Clarifying Questions to Ask Guidance

  • May tasks be reordered? No.
  • Does cooldown zero allow identical tasks on consecutive days? Yes.
  • Are idle days counted in the answer? Yes.

Examples

tasks = ["A","A"], cooldown = 2 -> 4
tasks = ["A","B","A"], cooldown = 2 -> 4
tasks = ["A","A","A"], cooldown = 0 -> 3
tasks = [], cooldown = 5 -> 0

Evaluation Focus

  • Preserves fixed task order.
  • Interprets the number of complete intervening days correctly through cooldown + 1 .
  • Handles zero cooldown, empty input, arbitrary string IDs, and large answers.
  • Runs in O(n) expected time with a hash map.

Extensions to Discuss

  1. How does the problem change if tasks may be reordered?
  2. How would per-task cooldown values alter the state?
  3. How could actual timestamps replace integer days?

Submit Your Answer to Earn 20XP

Sign in to leave a comment

Loading comments...