Scheduling

"Job sequencing, interval scheduling, CPU scheduling, task scheduling with dependencies, resource allocation."

Deep Dive Tutorial

Scheduling problems ask: given tasks with constraints (deadlines, durations, weights), which tasks to pick and in what order? The greedy insight almost always involves sorting — by deadline, end time, or weight ratio. When greedy alone isn't enough, add a heap for dynamic selection or DP + binary search for weighted variants.

Pattern 1: Activity Selection (Max Tasks, No Overlap)

key

Greedy rule: Sort by END time. Always pick the task that finishes earliest. Each pick eliminates as few future options as possible.

Proof: If any optimal solution doesn't pick the earliest-ending task, we can swap it in without making things worse.

Activity selection — max non-overlapping intervals

function maxActivities(intervals) {
    // Sort by end time
    intervals.sort((a, b) => a[1] - b[1]);
    let count = 0, lastEnd = -Infinity;
    for (const [start, end] of intervals) {
        if (start >= lastEnd) {
            count++;
            lastEnd = end;
        }
    }
    return count;
}

// Variant: minimum rooms needed (= max overlapping at any point)
function minRooms(intervals) {
    const starts = intervals.map(i => i[0]).sort((a,b)=>a-b);
    const ends   = intervals.map(i => i[1]).sort((a,b)=>a-b);
    let rooms = 0, maxRooms = 0, j = 0;
    for (let i = 0; i < intervals.length; i++) {
        while (ends[j] <= starts[i]) { rooms--; j++; }
        rooms++;
        maxRooms = Math.max(maxRooms, rooms);
    }
    return maxRooms;
}

Pattern 2: Deadline Scheduling (Max Profit Before Deadlines)

lightbulb

Greedy rule: Sort jobs by PROFIT descending. For each job, try to schedule it as late as possible before its deadline (use a Union-Find to find the latest free slot). This maximizes high-value jobs while respecting deadlines.

Weighted deadline scheduling with Union-Find

function maxProfit(jobs) {
    // jobs: [[deadline, profit], ...]
    jobs.sort((a, b) => b[1] - a[1]); // sort by profit desc
    const maxD = Math.max(...jobs.map(j => j[0]));
    const parent = Array.from({length: maxD + 2}, (_, i) => i);
    const find = (x) => parent[x] === x ? x : (parent[x] = find(parent[x]));

    let totalProfit = 0;
    for (const [deadline, profit] of jobs) {
        const slot = find(deadline); // latest free slot <= deadline
        if (slot > 0) {
            totalProfit += profit;
            parent[slot] = slot - 1; // mark slot as used, point to prev
        }
    }
    return totalProfit;
}

Pattern 3: Weighted Job Scheduling (DP + Binary Search)

Weighted job scheduling — O(n log n)

function weightedJobScheduling(jobs) {
    // jobs: [[start, end, weight], ...]
    jobs.sort((a, b) => a[1] - b[1]); // sort by end time
    const n = jobs.length;
    const dp = new Array(n + 1).fill(0);

    for (let i = 0; i < n; i++) {
        const [start, , weight] = jobs[i];
        // binary search: latest job that ends <= start of jobs[i]
        let lo = 0, hi = i;
        while (lo < hi) {
            const mid = (lo + hi + 1) >> 1;
            if (jobs[mid - 1][1] <= start) lo = mid;
            else hi = mid - 1;
        }
        // either take job i (dp[lo] + weight) or skip it (dp[i])
        dp[i + 1] = Math.max(dp[i], dp[lo] + weight);
    }
    return dp[n];
}

Pattern 4: Course Prerequisites (Topological Sort)

Topological sort (Kahn's BFS) for dependency scheduling

function canFinish(numCourses, prerequisites) {
    const graph = Array.from({length: numCourses}, () => []);
    const indegree = new Array(numCourses).fill(0);
    for (const [a, b] of prerequisites) {
        graph[b].push(a);
        indegree[a]++;
    }
    const queue = [];
    for (let i = 0; i < numCourses; i++)
        if (indegree[i] === 0) queue.push(i);

    let completed = 0;
    while (queue.length) {
        const node = queue.shift();
        completed++;
        for (const next of graph[node])
            if (--indegree[next] === 0) queue.push(next);
    }
    return completed === numCourses; // false = cycle exists
}

// Get order: same pattern, return the queue-appended order
function findOrder(numCourses, prerequisites) {
    // same setup as above, return order array
    // ... build graph + indegrees
    // return [...result] from queue processing
}