Finish Day: Schedule Tasks to Complete the Maximum Number Before End of Day Given Deadlines
Interview Experience
Problem
You have a list of tasks, each with a duration (minutes) and a deadline (minute of the day they must finish by). The day starts at minute 0. You can process only one task at a time. Maximize the number of tasks completed before their deadlines.
python
def max_tasks_finished(tasks: list[dict]) -> int:
# tasks: [{"name": str, "duration": int, "deadline": int}]
pass
Example:
tasks = [
{"name":"A", "duration":60, "deadline":120},
{"name":"B", "duration":30, "deadline":50},
{"name":"C", "duration":100, "deadline":200},
]
# Greedy: B (done at 30 < 50), A (done at 90 < 120), C (done at 190 < 200)
**output** -> 3
Approach
Sort by deadline (Earliest Deadline First). Greedily schedule tasks in deadline order, accumulating time. If adding a task would miss its deadline, skip it. EDF is optimal for maximizing task count with unit-equivalent tasks.
Follow-ups
1. Prove that Earliest Deadline First is optimal here, or describe a case where it fails.
2. Tasks now have integer priorities. You want to maximize total priority, not count. How does your algorithm change?
3. Some tasks are dependent -- Task C cannot start until Task A finishes. How do you incorporate dependencies?
4. The schedule must also include mandatory breaks (e.g., 30-minute lunch at minute 240). How do you insert them?
Full Details
Problem
You have a list of tasks, each with a duration (minutes) and a deadline (minute of the day they must finish by). The day starts at minute 0. You can process only one task at a time. Maximize the number of tasks completed before their deadlines.
python
def max_tasks_finished(tasks: list[dict]) -> int:
# tasks: [{"name": str, "duration": int, "deadline": int}]
pass
Example:
tasks = [
{"name":"A", "duration":60, "deadline":120},
{"name":"B", "duration":30, "deadline":50},
{"name":"C", "duration":100, "deadline":200},
]
# Greedy: B (done at 30 < 50), A (done at 90 < 120), C (done at 190 < 200)
**output** -> 3
Approach
Sort by deadline (Earliest Deadline First). Greedily schedule tasks in deadline order, accumulating time. If adding a task would miss its deadline, skip it. EDF is optimal for maximizing task count with unit-equivalent tasks.
Follow-ups
1. Prove that Earliest Deadline First is optimal here, or describe a case where it fails.
2. Tasks now have integer priorities. You want to maximize total priority, not count. How does your algorithm change?
3. Some tasks are dependent -- Task C cannot start until Task A finishes. How do you incorporate dependencies?
4. The schedule must also include mandatory breaks (e.g., 30-minute lunch at minute 240). How do you insert them?
About This Question
This is a candidate experience report from a airtable interview during the phone round.
It covers the following topics: Coding, Greedy, Phone, Onsite .