Meeting Rooms III (K Machines, Earliest Available)

🎯

Meeting Rooms III (K Machines, Earliest Available)

hardHEAPAmazonGoogle

Imagine you manage a factory with K identical machines and a queue of jobs arriving at different times, each requiring some processing time. You want to assign each job to the earliest available machine to minimize waiting.

💡 This problem involves scheduling jobs on multiple machines by always assigning the next job to the machine that becomes free the earliest. Beginners often struggle because it requires managing two heaps simultaneously and understanding how to track machine availability efficiently.

📋

Problem Statement

Given an integer K representing the number of identical machines and a list of jobs where each job is represented as [startTime, duration], assign each job to a machine such that each machine processes jobs sequentially without overlap. For each job, assign it to the machine that becomes available the earliest (if multiple machines are free at the job's start time, assign to the machine with the smallest index). Return an array where the ith element is the index of the machine assigned to the ith job.

1 ≤ K ≤ 10^51 ≤ number of jobs (n) ≤ 10^50 ≤ startTime[i] ≤ 10^91 ≤ duration[i] ≤ 10^6

💡

Example

Input"K = 2, jobs = [[0, 5], [1, 2], [5, 3]]"

Output[0, 1, 0]

Job 0 starts at 0 on machine 0. Job 1 starts at 1 on machine 1. Job 2 starts at 5; machine 0 is free at 5, so assign job 2 to machine 0.

• K = 1, multiple jobs with overlapping times → all assigned sequentially to machine 0
• Jobs with the same start time → assign to machines with smallest index first
• Jobs with zero duration (if allowed) → machine becomes free immediately
• Large K with fewer jobs → some machines remain unused

⚠️

Common Mistakes

Not sorting jobs by start time

Machines may be assigned jobs out of chronological order, causing incorrect scheduling

✅ Always sort jobs by start time before processing

Not freeing machines before assigning new jobs

Machines that should be free remain marked busy, causing unnecessary waiting or errors

✅ Before assigning a job, pop all machines from running heap whose finish time ≤ job start and push them back to available heap

Using a single heap without tracking machine indices properly

Cannot break ties by machine index, leading to incorrect assignments

✅ Use two heaps or store machine indices in the heap to break ties correctly

Updating finish time incorrectly (e.g., using max of start and machine free time)

Finish times may be overestimated, causing machines to appear busy longer than needed

✅ Since machines are freed before assignment, finish time = job start + duration is correct

Not handling tie-breaks when multiple machines are free at the same time

Jobs may be assigned to machines with higher indices incorrectly

✅ Use min-heap of machine indices for available machines to always pick smallest index

🧠

Brute Force (Simulate Machine Availability with Linear Search)

💡 This approach exists to build intuition by simulating the problem directly without advanced data structures. It helps understand the scheduling constraints but is inefficient for large inputs.

Intuition

For each job, check all machines to find the earliest available one and assign the job to it. Update that machine's next available time accordingly.

Algorithm

1. Initialize an array to track the next available time for each machine, all starting at 0.
2. For each job in order, iterate over all machines to find the one with the earliest available time that is ≤ job's start time or the earliest overall.
3. Assign the job to that machine and update the machine's next available time to max(machine's available time, job start) + job duration.
4. Record the assigned machine index for each job.

💡 The nested iteration over machines for each job makes this approach straightforward but inefficient, especially when K or n is large.

</>

Code

from typing import List

def assign_jobs_brute_force(K: int, jobs: List[List[int]]) -> List[int]:
    n = len(jobs)
    machine_next_free = [0] * K
    result = [0] * n
    for i, (start, duration) in enumerate(jobs):
        earliest_machine = 0
        earliest_time = float('inf')
        for m in range(K):
            available_time = machine_next_free[m]
            # The machine can start the job at max of its free time and job start
            start_time = max(available_time, start)
            if start_time < earliest_time or (start_time == earliest_time and m < earliest_machine):
                earliest_time = start_time
                earliest_machine = m
        machine_next_free[earliest_machine] = earliest_time + duration
        result[i] = earliest_machine
    return result

# Example usage
if __name__ == '__main__':
    K = 2
    jobs = [[0,5],[1,2],[5,3]]
    print(assign_jobs_brute_force(K, jobs))  # Output: [0, 1, 0]

Line Notes

machine_next_free = [0] * KInitialize all machines as free at time 0

for i, (start, duration) in enumerate(jobs):Process jobs in given order

for m in range(K):Check each machine to find earliest available

start_time = max(available_time, start)Job can only start after machine is free and job arrives

if start_time < earliest_time or (start_time == earliest_time and m < earliest_machine):Choose machine with earliest start time, break ties by machine index

machine_next_free[earliest_machine] = earliest_time + durationUpdate machine's next free time after assigning job

result[i] = earliest_machineRecord assigned machine for current job

import java.util.*;

public class MeetingRoomsIII {
    public static int[] assignJobsBruteForce(int K, int[][] jobs) {
        int n = jobs.length;
        int[] machineNextFree = new int[K];
        int[] result = new int[n];
        for (int i = 0; i < n; i++) {
            int start = jobs[i][0];
            int duration = jobs[i][1];
            int earliestMachine = 0;
            int earliestTime = Integer.MAX_VALUE;
            for (int m = 0; m < K; m++) {
                int availableTime = machineNextFree[m];
                int startTime = Math.max(availableTime, start);
                if (startTime < earliestTime || (startTime == earliestTime && m < earliestMachine)) {
                    earliestTime = startTime;
                    earliestMachine = m;
                }
            }
            machineNextFree[earliestMachine] = earliestTime + duration;
            result[i] = earliestMachine;
        }
        return result;
    }

    public static void main(String[] args) {
        int K = 2;
        int[][] jobs = {{0,5},{1,2},{5,3}};
        System.out.println(Arrays.toString(assignJobsBruteForce(K, jobs)));
    }
}

Line Notes

int[] machineNextFree = new int[K];Track when each machine becomes free

for (int i = 0; i < n; i++) {Iterate over all jobs

for (int m = 0; m < K; m++) {Check all machines for earliest availability

int startTime = Math.max(availableTime, start);Job start time must respect machine availability

if (startTime < earliestTime || (startTime == earliestTime && m < earliestMachine)) {Choose earliest machine, break ties by index

machineNextFree[earliestMachine] = earliestTime + duration;Update machine's next free time

result[i] = earliestMachine;Assign machine to job

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> assignJobsBruteForce(int K, const vector<vector<int>>& jobs) {
    int n = jobs.size();
    vector<int> machineNextFree(K, 0);
    vector<int> result(n);
    for (int i = 0; i < n; i++) {
        int start = jobs[i][0];
        int duration = jobs[i][1];
        int earliestMachine = 0;
        int earliestTime = INT_MAX;
        for (int m = 0; m < K; m++) {
            int availableTime = machineNextFree[m];
            int startTime = max(availableTime, start);
            if (startTime < earliestTime || (startTime == earliestTime && m < earliestMachine)) {
                earliestTime = startTime;
                earliestMachine = m;
            }
        }
        machineNextFree[earliestMachine] = earliestTime + duration;
        result[i] = earliestMachine;
    }
    return result;
}

int main() {
    int K = 2;
    vector<vector<int>> jobs = {{0,5},{1,2},{5,3}};
    vector<int> res = assignJobsBruteForce(K, jobs);
    for (int m : res) cout << m << ' ';
    cout << '\n';
    return 0;
}

Line Notes

vector<int> machineNextFree(K, 0);Initialize all machines free at time 0

for (int i = 0; i < n; i++) {Process each job sequentially

for (int m = 0; m < K; m++) {Check every machine for earliest availability

int startTime = max(availableTime, start);Job start time respects machine availability

if (startTime < earliestTime || (startTime == earliestTime && m < earliestMachine)) {Pick earliest machine, tie-break by index

machineNextFree[earliestMachine] = earliestTime + duration;Update machine's next free time

result[i] = earliestMachine;Assign machine index to job

function assignJobsBruteForce(K, jobs) {
    const n = jobs.length;
    const machineNextFree = new Array(K).fill(0);
    const result = new Array(n);
    for (let i = 0; i < n; i++) {
        const [start, duration] = jobs[i];
        let earliestMachine = 0;
        let earliestTime = Infinity;
        for (let m = 0; m < K; m++) {
            const availableTime = machineNextFree[m];
            const startTime = Math.max(availableTime, start);
            if (startTime < earliestTime || (startTime === earliestTime && m < earliestMachine)) {
                earliestTime = startTime;
                earliestMachine = m;
            }
        }
        machineNextFree[earliestMachine] = earliestTime + duration;
        result[i] = earliestMachine;
    }
    return result;
}

// Example usage
const K = 2;
const jobs = [[0,5],[1,2],[5,3]];
console.log(assignJobsBruteForce(K, jobs)); // Output: [0, 1, 0]

Line Notes

const machineNextFree = new Array(K).fill(0);Initialize machines as free at time 0

for (let i = 0; i < n; i++) {Iterate over each job

for (let m = 0; m < K; m++) {Check all machines for earliest availability

const startTime = Math.max(availableTime, start);Job start respects machine availability

if (startTime < earliestTime || (startTime === earliestTime && m < earliestMachine)) {Choose earliest machine, tie-break by index

machineNextFree[earliestMachine] = earliestTime + duration;Update machine's next free time

result[i] = earliestMachine;Assign machine index to job

⏱

Complexity

TimeO(n*K)

SpaceO(K + n)

For each of the n jobs, we scan all K machines to find earliest availability, resulting in O(n*K) time. We store machine availability and result arrays.

💡 If n=100,000 and K=100,000, this means 10 billion operations, which is too slow for interviews.

Interview Verdict: TLE

This approach is too slow for large inputs but is useful to understand the problem and constraints before optimizing.

🧠

Better Approach Using Two Min-Heaps (Available and Running Machines)

💡 This approach uses two priority queues (min-heaps) to efficiently track which machines are free and which are busy, enabling quick assignment of jobs to earliest available machines.

Intuition

Maintain a min-heap of available machines sorted by machine index, and a min-heap of running machines sorted by their next free time. For each job, free up machines that have completed their jobs by the job's start time, then assign the job to the earliest available machine.

Algorithm

1. Initialize a min-heap of available machines with all machine indices (0 to K-1).
2. Initialize an empty min-heap for running machines, storing tuples of (free_time, machine_index).
3. Sort jobs by their start time if not already sorted.
4. For each job, pop machines from running heap whose free_time ≤ job start time and push them back to available heap.
5. Pop the machine with smallest index from available heap and assign the job to it.
6. Push the machine into running heap with updated free_time = job start + duration.
7. Record the assigned machine index for each job.

💡 This approach cleverly uses two heaps to efficiently manage machine states and quickly find the earliest available machine.

</>

Code

import heapq
from typing import List

def assign_jobs_heap(K: int, jobs: List[List[int]]) -> List[int]:
    n = len(jobs)
    # Jobs are assumed sorted by start time; if not, sort with indices
    indexed_jobs = sorted(enumerate(jobs), key=lambda x: x[1][0])
    available = list(range(K))
    heapq.heapify(available)  # min-heap of machine indices
    running = []  # min-heap of (free_time, machine_index)
    result = [0] * n

    for idx, (start, duration) in indexed_jobs:
        # Free machines that have completed jobs by start time
        while running and running[0][0] <= start:
            free_time, machine = heapq.heappop(running)
            heapq.heappush(available, machine)
        # Assign job to earliest available machine
        machine = heapq.heappop(available)
        finish_time = start + duration
        heapq.heappush(running, (finish_time, machine))
        result[idx] = machine
    return result

# Example usage
if __name__ == '__main__':
    K = 2
    jobs = [[0,5],[1,2],[5,3]]
    print(assign_jobs_heap(K, jobs))  # Output: [0, 1, 0]

Line Notes

indexed_jobs = sorted(enumerate(jobs), key=lambda x: x[1][0])Sort jobs by start time while keeping original indices

available = list(range(K))Initialize all machines as available by their indices

heapq.heapify(available)Create a min-heap for available machines

while running and running[0][0] <= start:Free machines that have completed jobs before current job starts

machine = heapq.heappop(available)Assign job to machine with smallest index

finish_time = start + durationCalculate when machine will be free after current job

heapq.heappush(running, (finish_time, machine))Add machine to running heap with updated free time

result[idx] = machineRecord assigned machine for job

import java.util.*;

public class MeetingRoomsIII {
    public static int[] assignJobsHeap(int K, int[][] jobs) {
        int n = jobs.length;
        Integer[] indices = new Integer[n];
        for (int i = 0; i < n; i++) indices[i] = i;
        Arrays.sort(indices, Comparator.comparingInt(i -> jobs[i][0]));

        PriorityQueue<Integer> available = new PriorityQueue<>();
        for (int i = 0; i < K; i++) available.offer(i);
        PriorityQueue<int[]> running = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        int[] result = new int[n];

        for (int idx : indices) {
            int start = jobs[idx][0];
            int duration = jobs[idx][1];
            while (!running.isEmpty() && running.peek()[0] <= start) {
                available.offer(running.poll()[1]);
            }
            int machine = available.poll();
            int finishTime = start + duration;
            running.offer(new int[]{finishTime, machine});
            result[idx] = machine;
        }
        return result;
    }

    public static void main(String[] args) {
        int K = 2;
        int[][] jobs = {{0,5},{1,2},{5,3}};
        System.out.println(Arrays.toString(assignJobsHeap(K, jobs)));
    }
}

Line Notes

Integer[] indices = new Integer[n];Create array to store original job indices

Arrays.sort(indices, Comparator.comparingInt(i -> jobs[i][0]));Sort jobs by start time using indices

PriorityQueue<Integer> available = new PriorityQueue<>();Min-heap for available machines by index

while (!running.isEmpty() && running.peek()[0] <= start) {Free machines that finished before job start

int machine = available.poll();Assign job to earliest available machine

int finishTime = start + duration;Calculate machine's next free time

running.offer(new int[]{finishTime, machine});Add machine to running heap

result[idx] = machine;Record assigned machine

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

vector<int> assignJobsHeap(int K, const vector<vector<int>>& jobs) {
    int n = jobs.size();
    vector<int> indices(n);
    for (int i = 0; i < n; i++) indices[i] = i;
    sort(indices.begin(), indices.end(), [&](int a, int b) {
        return jobs[a][0] < jobs[b][0];
    });

    priority_queue<int, vector<int>, greater<int>> available;
    for (int i = 0; i < K; i++) available.push(i);
    // running stores pairs of (free_time, machine_index)
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> running;
    vector<int> result(n);

    for (int idx : indices) {
        int start = jobs[idx][0];
        int duration = jobs[idx][1];
        while (!running.empty() && running.top().first <= start) {
            available.push(running.top().second);
            running.pop();
        }
        int machine = available.top();
        available.pop();
        int finishTime = start + duration;
        running.emplace(finishTime, machine);
        result[idx] = machine;
    }
    return result;
}

int main() {
    int K = 2;
    vector<vector<int>> jobs = {{0,5},{1,2},{5,3}};
    vector<int> res = assignJobsHeap(K, jobs);
    for (int m : res) cout << m << ' ';
    cout << '\n';
    return 0;
}

Line Notes

vector<int> indices(n);Store original job indices for sorting

sort(indices.begin(), indices.end(), [&](int a, int b) {Sort jobs by start time using indices

priority_queue<int, vector<int>, greater<int>> available;Min-heap for available machines by index

while (!running.empty() && running.top().first <= start) {Free machines that finished before job start

int machine = available.top();Assign job to earliest available machine

int finishTime = start + duration;Calculate machine's next free time

running.emplace(finishTime, machine);Add machine to running heap

result[idx] = machine;Record assigned machine

function assignJobsHeap(K, jobs) {
    const n = jobs.length;
    const indices = [...Array(n).keys()];
    indices.sort((a, b) => jobs[a][0] - jobs[b][0]);

    const available = [];
    for (let i = 0; i < K; i++) available.push(i);
    available.sort((a,b) => a - b);

    const running = [];

    function heapPush(arr, val, compare) {
        arr.push(val);
        let i = arr.length - 1;
        while (i > 0) {
            let p = Math.floor((i - 1) / 2);
            if (compare(arr[p], arr[i]) <= 0) break;
            [arr[p], arr[i]] = [arr[i], arr[p]];
            i = p;
        }
    }

    function heapPop(arr, compare) {
        const top = arr[0];
        const last = arr.pop();
        if (arr.length > 0) {
            arr[0] = last;
            let i = 0;
            while (true) {
                let left = 2 * i + 1, right = 2 * i + 2, smallest = i;
                if (left < arr.length && compare(arr[left], arr[smallest]) < 0) smallest = left;
                if (right < arr.length && compare(arr[right], arr[smallest]) < 0) smallest = right;
                if (smallest === i) break;
                [arr[i], arr[smallest]] = [arr[smallest], arr[i]];
                i = smallest;
            }
        }
        return top;
    }

    // Min-heap compare functions
    const compareAvailable = (a,b) => a - b;
    const compareRunning = (a,b) => a[0] - b[0];

    // Heapify available
    available.sort((a,b) => a-b);

    const result = new Array(n);

    for (const idx of indices) {
        const [start, duration] = jobs[idx];
        // Free machines that finished before start
        while (running.length > 0 && running[0][0] <= start) {
            const [_, machine] = heapPop(running, compareRunning);
            heapPush(available, machine, compareAvailable);
        }
        const machine = heapPop(available, compareAvailable);
        const finishTime = start + duration;
        heapPush(running, [finishTime, machine], compareRunning);
        result[idx] = machine;
    }
    return result;
}

// Example usage
const K = 2;
const jobs = [[0,5],[1,2],[5,3]];
console.log(assignJobsHeap(K, jobs)); // Output: [0, 1, 0]

Line Notes

const indices = [...Array(n).keys()];Create array of job indices for sorting

indices.sort((a, b) => jobs[a][0] - jobs[b][0]);Sort jobs by start time using indices

const available = []; for (let i = 0; i < K; i++) available.push(i);Initialize available machines by index

while (running.length > 0 && running[0][0] <= start) {Free machines that finished before job start

const machine = heapPop(available, compareAvailable);Assign job to earliest available machine

const finishTime = start + duration;Calculate machine's next free time

heapPush(running, [finishTime, machine], compareRunning);Add machine to running heap

result[idx] = machine;Record assigned machine

⏱

Complexity

TimeO(n log K)

SpaceO(K + n)

Each job causes at most one push and pop on heaps of size up to K, so O(n log K) time. Space stores heaps and result arrays.

💡 For n=100,000 and K=100,000, this reduces operations to about 1.5 million, which is feasible.

Interview Verdict: Accepted

This approach is efficient and practical for large inputs, demonstrating mastery of heap data structures.

🧠

Optimal Approach with Event Sorting and Single Min-Heap

💡 This approach optimizes further by processing jobs in order and using a single min-heap to track running machines, freeing machines as jobs complete, and assigning jobs greedily.

Intuition

Sort jobs by start time. Use a min-heap to track machines currently running jobs by their finish time. Before assigning a job, free all machines that have completed jobs by the job's start time. Assign the job to the earliest available machine (lowest index).

Algorithm

1. Sort jobs by their start time, keeping track of original indices.
2. Initialize a min-heap of available machines by their indices.
3. Initialize an empty min-heap for running machines storing (finish_time, machine_index).
4. For each job in sorted order, pop from running heap all machines that finished before job start and push them back to available heap.
5. Pop the machine with smallest index from available heap and assign the job.
6. Push the machine into running heap with updated finish time = job start + duration.
7. Record the assigned machine index for each job.

💡 This approach merges the two-heap method into a clean, linear pass over jobs with efficient machine management.

</>

Code

import heapq
from typing import List

def assign_jobs_optimal(K: int, jobs: List[List[int]]) -> List[int]:
    n = len(jobs)
    indexed_jobs = sorted(enumerate(jobs), key=lambda x: x[1][0])
    available = list(range(K))
    heapq.heapify(available)
    running = []
    result = [0] * n

    for idx, (start, duration) in indexed_jobs:
        while running and running[0][0] <= start:
            _, machine = heapq.heappop(running)
            heapq.heappush(available, machine)
        machine = heapq.heappop(available)
        finish_time = start + duration
        heapq.heappush(running, (finish_time, machine))
        result[idx] = machine
    return result

# Example usage
if __name__ == '__main__':
    K = 2
    jobs = [[0,5],[1,2],[5,3]]
    print(assign_jobs_optimal(K, jobs))  # Output: [0, 1, 0]

Line Notes

indexed_jobs = sorted(enumerate(jobs), key=lambda x: x[1][0])Sort jobs by start time, keep original indices

available = list(range(K))Initialize all machines as available

heapq.heapify(available)Create min-heap for available machines by index

while running and running[0][0] <= start:Free machines that finished before current job start

machine = heapq.heappop(available)Assign job to earliest available machine

finish_time = start + durationCalculate machine's next free time

heapq.heappush(running, (finish_time, machine))Add machine to running heap

result[idx] = machineRecord assigned machine

import java.util.*;

public class MeetingRoomsIII {
    public static int[] assignJobsOptimal(int K, int[][] jobs) {
        int n = jobs.length;
        Integer[] indices = new Integer[n];
        for (int i = 0; i < n; i++) indices[i] = i;
        Arrays.sort(indices, Comparator.comparingInt(i -> jobs[i][0]));

        PriorityQueue<Integer> available = new PriorityQueue<>();
        for (int i = 0; i < K; i++) available.offer(i);
        PriorityQueue<int[]> running = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        int[] result = new int[n];

        for (int idx : indices) {
            int start = jobs[idx][0];
            int duration = jobs[idx][1];
            while (!running.isEmpty() && running.peek()[0] <= start) {
                available.offer(running.poll()[1]);
            }
            int machine = available.poll();
            int finishTime = start + duration;
            running.offer(new int[]{finishTime, machine});
            result[idx] = machine;
        }
        return result;
    }

    public static void main(String[] args) {
        int K = 2;
        int[][] jobs = {{0,5},{1,2},{5,3}};
        System.out.println(Arrays.toString(assignJobsOptimal(K, jobs)));
    }
}

Line Notes

Integer[] indices = new Integer[n];Store job indices for sorting

Arrays.sort(indices, Comparator.comparingInt(i -> jobs[i][0]));Sort jobs by start time

PriorityQueue<Integer> available = new PriorityQueue<>();Min-heap for available machines

while (!running.isEmpty() && running.peek()[0] <= start) {Free machines that finished before job start

int machine = available.poll();Assign job to earliest available machine

int finishTime = start + duration;Calculate machine's next free time

running.offer(new int[]{finishTime, machine});Add machine to running heap

result[idx] = machine;Record assigned machine

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

vector<int> assignJobsOptimal(int K, const vector<vector<int>>& jobs) {
    int n = jobs.size();
    vector<int> indices(n);
    for (int i = 0; i < n; i++) indices[i] = i;
    sort(indices.begin(), indices.end(), [&](int a, int b) {
        return jobs[a][0] < jobs[b][0];
    });

    priority_queue<int, vector<int>, greater<int>> available;
    for (int i = 0; i < K; i++) available.push(i);
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> running;
    vector<int> result(n);

    for (int idx : indices) {
        int start = jobs[idx][0];
        int duration = jobs[idx][1];
        while (!running.empty() && running.top().first <= start) {
            available.push(running.top().second);
            running.pop();
        }
        int machine = available.top();
        available.pop();
        int finishTime = start + duration;
        running.emplace(finishTime, machine);
        result[idx] = machine;
    }
    return result;
}

int main() {
    int K = 2;
    vector<vector<int>> jobs = {{0,5},{1,2},{5,3}};
    vector<int> res = assignJobsOptimal(K, jobs);
    for (int m : res) cout << m << ' ';
    cout << '\n';
    return 0;
}

Line Notes

vector<int> indices(n);Store job indices for sorting

sort(indices.begin(), indices.end(), [&](int a, int b) {Sort jobs by start time

priority_queue<int, vector<int>, greater<int>> available;Min-heap for available machines

while (!running.empty() && running.top().first <= start) {Free machines that finished before job start

int machine = available.top();Assign job to earliest available machine

int finishTime = start + duration;Calculate machine's next free time

running.emplace(finishTime, machine);Add machine to running heap

result[idx] = machine;Record assigned machine

function assignJobsOptimal(K, jobs) {
    const n = jobs.length;
    const indices = [...Array(n).keys()];
    indices.sort((a, b) => jobs[a][0] - jobs[b][0]);

    const available = [];
    for (let i = 0; i < K; i++) available.push(i);
    available.sort((a,b) => a-b);

    const running = [];

    function heapPush(arr, val, compare) {
        arr.push(val);
        let i = arr.length - 1;
        while (i > 0) {
            let p = Math.floor((i - 1) / 2);
            if (compare(arr[p], arr[i]) <= 0) break;
            [arr[p], arr[i]] = [arr[i], arr[p]];
            i = p;
        }
    }

    function heapPop(arr, compare) {
        const top = arr[0];
        const last = arr.pop();
        if (arr.length > 0) {
            arr[0] = last;
            let i = 0;
            while (true) {
                let left = 2 * i + 1, right = 2 * i + 2, smallest = i;
                if (left < arr.length && compare(arr[left], arr[smallest]) < 0) smallest = left;
                if (right < arr.length && compare(arr[right], arr[smallest]) < 0) smallest = right;
                if (smallest === i) break;
                [arr[i], arr[smallest]] = [arr[smallest], arr[i]];
                i = smallest;
            }
        }
        return top;
    }

    const compareAvailable = (a,b) => a - b;
    const compareRunning = (a,b) => a[0] - b[0];

    available.sort((a,b) => a-b);

    const result = new Array(n);

    for (const idx of indices) {
        const [start, duration] = jobs[idx];
        while (running.length > 0 && running[0][0] <= start) {
            const [_, machine] = heapPop(running, compareRunning);
            heapPush(available, machine, compareAvailable);
        }
        const machine = heapPop(available, compareAvailable);
        const finishTime = start + duration;
        heapPush(running, [finishTime, machine], compareRunning);
        result[idx] = machine;
    }
    return result;
}

// Example usage
const K = 2;
const jobs = [[0,5],[1,2],[5,3]];
console.log(assignJobsOptimal(K, jobs)); // Output: [0, 1, 0]

Line Notes

const indices = [...Array(n).keys()];Create array of job indices for sorting

indices.sort((a, b) => jobs[a][0] - jobs[b][0]);Sort jobs by start time

const available = []; for (let i = 0; i < K; i++) available.push(i);Initialize available machines

while (running.length > 0 && running[0][0] <= start) {Free machines that finished before job start

const machine = heapPop(available, compareAvailable);Assign job to earliest available machine

const finishTime = start + duration;Calculate machine's next free time

heapPush(running, [finishTime, machine], compareRunning);Add machine to running heap

result[idx] = machine;Record assigned machine

⏱

Complexity

TimeO(n log K)

SpaceO(K + n)

Sorting jobs takes O(n log n), heap operations per job take O(log K), overall O(n log K) dominates. Space stores heaps and results.

💡 This approach is efficient for large inputs and uses minimal data structures, making it ideal for interviews.

Interview Verdict: Accepted

This is the cleanest and most optimal approach, demonstrating strong understanding of heaps and greedy scheduling.

📊

All Approaches - One-Glance Tradeoffs

💡 In 95% of interviews, code the optimal heap-based approach (Approach 3). Use brute force only to explain the problem and two-heap approach to show progression.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n*K)	O(K + n)	No	N/A	Mention only - never code due to inefficiency
2. Two Min-Heaps	O(n log K)	O(K + n)	No	Yes	Good to explain and code if interviewer wants heap usage
3. Optimal Single Pass with Min-Heaps	O(n log K)	O(K + n)	No	Yes	Best approach to code in interviews

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Clarify the problem and constraints with the interviewer.Explain the brute force approach to show understanding of the problem.Discuss inefficiencies and motivate the use of heaps.Present the two-heap approach and explain how it improves efficiency.Finally, present the optimal approach and code it carefully.Test your code with examples and edge cases.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

The interviewer tests your ability to manage multiple resources efficiently, use heaps correctly, and optimize from brute force to optimal solutions.

Common Follow-ups

• What if jobs can be preempted? → Requires different scheduling, possibly priority queues with preemption.
• How to handle jobs arriving out of order? → Sort jobs by start time first.
• What if machines have different speeds? → Adjust finish time calculation accordingly.
• How to track total idle time per machine? → Maintain additional counters updated when machines become free.

💡 These follow-ups test your ability to adapt the solution to variations and demonstrate deeper understanding of scheduling.

🔍

Pattern Recognition

When to Use

1) Multiple resources (machines) to assign jobs/tasks; 2) Need earliest available resource; 3) Jobs have start times and durations; 4) Tie-break by resource index.

Signature Phrases

earliest available machineassign jobs to machinesK identical machinesstart time and duration

NOT This Pattern When

Problems that require DP or backtracking for complex constraints, or those without resource assignment.

Similar Problems

Meeting Rooms II - scheduling intervals with minimum roomsCar Pooling - managing capacity over timeCPU Scheduling - assigning tasks to processors

Practice

1. You are given two sorted arrays and need to find the k-th smallest sum formed by adding one element from each array. Which approach guarantees an optimal solution in terms of time complexity for large input sizes?

easy

A. Use binary search on the sum range combined with a counting function to find how many pairs have sums less than or equal to mid.

B. Use dynamic programming to build a table of sums and select the k-th smallest.

C. Use a greedy approach by always picking the smallest available sum without revisiting pairs.

D. Generate all possible sums, sort them, and pick the k-th smallest sum.

Solution

1. Step 1: Understand problem constraints

   Brute force (generating all sums) is too slow for large inputs.

2. Step 2: Identify efficient approach

   Binary search on sum range with counting pairs ≤ mid efficiently narrows down the k-th smallest sum.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Binary search reduces search space logarithmically [OK]

Hint: Binary search on sums beats brute force for large inputs [OK]

Common Mistakes:

• Assuming greedy approach always works
• Using DP which is inefficient here

2. You are given k sorted lists of integers. Your task is to find the smallest range that includes at least one number from each of the k lists. Which algorithmic approach guarantees an optimal solution with efficient time complexity?

easy

A. Use a min-heap to track the current minimum element among the heads of each list while maintaining the current maximum, updating the range as you iterate.

B. Apply a greedy approach by always picking the smallest element from any list and expanding the range until all lists are covered.

C. Sort all elements from all lists into one array and use a dynamic programming approach to find the minimal range covering all lists.

D. Use a brute force approach enumerating all combinations of elements from each list and selecting the minimal range.

Solution

1. Step 1: Understand the problem constraints

   The problem requires finding a range that covers at least one element from each of the k sorted lists, minimizing the range size.

2. Step 2: Identify the optimal approach

   Using a min-heap to track the smallest current element from each list and maintaining the maximum element seen so far allows efficient updates of the range while iterating through the lists.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Min-heap approach efficiently tracks min and max for optimal range [OK]

Hint: Min-heap tracks min and max for optimal range [OK]

Common Mistakes:

• Thinking brute force is feasible for large k
• Assuming greedy picking smallest element always works
• Confusing DP applicability here

3. The following code attempts to merge k sorted arrays using divide and conquer. Which line contains a subtle bug that causes incorrect output when the number of arrays is odd?

medium

A. Line 5: for i in range(0, len(arrays), 2):

B. Line 8: merged_arrays.append(merge_two_arrays(arr1, arr2))

C. Line 7: arr2 = arrays[i+1]

D. Line 10: return arrays[0]

Solution

1. Step 1: Identify handling of odd number of arrays

   When number of arrays is odd, accessing arrays[i+1] without check causes IndexError or misses last array.

2. Step 2: Correct fix

   Use conditional: arr2 = arrays[i+1] if i+1 < len(arrays) else [] to handle last array properly.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Line 7 lacks boundary check -> bug on odd arrays [OK]

Hint: Check array bounds when accessing pairs in loop [OK]

Common Mistakes:

• Forgetting boundary check for last array
• Merging empty array incorrectly
• Returning wrong array index

4. Suppose you want to merge k sorted arrays but now each array can contain duplicate elements that can be reused multiple times in the final merged array. Which modification to the divide and conquer approach correctly handles this scenario?

hard

A. Use a min heap to repeatedly extract the smallest element and reinsert it if duplicates can be reused.

B. Modify merge_two_arrays to allow unlimited reuse by appending elements multiple times without advancing indices.

C. No change needed; the existing divide and conquer merge works correctly with duplicates and reuse.

D. Switch to a dynamic programming approach to track counts of duplicates and reuse them optimally.

Solution

1. Step 1: Understand reuse of duplicates

   Reusing duplicates means elements can appear multiple times beyond their original count, which standard merging does not support.

2. Step 2: Evaluate approaches

   Divide and conquer merges fixed arrays once, so it cannot handle reuse. Modifying merge_two_arrays to append without advancing indices causes infinite loops. Dynamic programming is not suitable here. Using a min heap allows extracting smallest elements and reinserting them if reuse is allowed, correctly handling duplicates and reuse.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Min heap supports repeated extraction and reinsertion -> handles reuse [OK]

Hint: Reuse requires dynamic extraction and reinsertion, not fixed merges [OK]

Common Mistakes:

• Assuming divide and conquer handles reuse
• Infinite loops by not advancing indices
• Using DP unnecessarily

5. Suppose the problem changes: now you want to find the nth ugly number but you can reuse the same ugly number multiple times in generating new numbers (i.e., duplicates allowed). Which modification to the min-heap approach correctly handles this variant without losing correctness or efficiency?

hard

A. Remove the 'seen' set entirely and push all generated numbers into the heap, allowing duplicates.

B. Keep the 'seen' set but reset it after every iteration to allow reuse of numbers in the next iteration.

C. Use a counter map to track how many times each number is generated and only push if count is below a threshold.

D. Keep the 'seen' set as is to avoid duplicates, since duplicates do not affect correctness or efficiency.

Solution

1. Step 1: Understand the variant allowing duplicates

   Allowing reuse means duplicates are valid and should be generated and processed multiple times.

2. Step 2: Modify the algorithm accordingly

   Removing the 'seen' set allows duplicates to be pushed and popped, correctly reflecting the new problem constraints.

3. Step 3: Consider efficiency

   Though duplicates increase heap size, this is necessary to correctly generate all numbers under the new rules.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Removing 'seen' allows duplicates as required [OK]

Hint: Allow duplicates by removing 'seen' when reuse is allowed [OK]

Common Mistakes:

• Keeping 'seen' and missing duplicates
• Resetting 'seen' incorrectly
• Using counters unnecessarily