Efficient Deployments: Schedule Deployments to Minimize Peak Concurrent Running Jobs

Question

## Problem

You are given a list of deployment jobs, each with a start time and end time (both inclusive, in minutes). You can delay any job's start by any non-negative integer amount. Find the minimum possible peak number of concurrently running jobs across any schedule.

Assume each job takes exactly `(end - start + 1)` minutes and must run for its full duration without interruption.

```python
from typing import List

def min_peak_concurrent(jobs: List[List[int]]) -> int:
    # jobs: [[start, end], ...]
    # return: minimum achievable peak concurrent count
    pass
```

**Example:**
```
Input: [[0,2],[0,2],[0,2]]
Without delay: 3 jobs all run t=0..2, peak=3
With delay:    job1 at 0-2, job2 at 3-5, job3 at 6-8, peak=1
Output: 1
```

**Note:** If jobs MUST start at their given start times, output is the maximum overlap; relaxed version above allows rescheduling.

## Follow-ups

1. What is the lower bound on peak concurrency if you cannot delay any job?
2. How would you solve the fixed-schedule version (no delays allowed) efficiently using a sweep line?
3. What if there is a hard deadline by which each job must finish — does this become NP-hard?
4. How does this relate to the interval scheduling and bin packing problems?

Efficient Deployments: Schedule Deployments to Minimize Peak Concurrent Running Jobs

Question Details

Full Details

Topics

More from Snowflake