Interval Scheduling for Restaurant Chefs | Dataford Interview Questions

ThoughtSpot receives customer requests that must be prepared during specified time intervals. Each chef can cook at most one request at a time. Given all request intervals, return the minimum number of chefs required so every request can be cooked within its interval.

Assume each interval represents the complete period during which one chef is occupied. Intervals use half-open notation [start, end), so a chef finishing at time t can immediately begin a request starting at time t.

Formal Specification

Implement minimum_chefs(requests), where requests is a list of intervals. Each interval is a two-element list [start, end] containing integer timestamps. Return an integer representing the minimum number of chefs needed.

Constraints

0 <= len(requests) <= 2 * 10^5
Each interval contains exactly two integers, start and end
0 <= start < end <= 10^9
Intervals are not necessarily sorted
Intervals are half-open: [start, end)

Function Signature

def minimum_chefs(requests):

Your question is Interval Scheduling for Restaurant Chefs. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem

Formal Specification

Constraints

0 <= len(requests) <= 2 * 10^5
Each interval contains exactly two integers, start and end
0 <= start < end <= 10^9
Intervals are not necessarily sorted
Intervals are half-open: [start, end)

Function Signature

def minimum_chefs(requests):

Your question is Interval Scheduling for Restaurant Chefs. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.