Problem

You are given a set of n jobs, given as arrays:

  • deadline[]: An array where deadline[i] represents the deadline of job i and  deadline (di ≥ 1),
  • profit[]: An array where profit[i] represents the profit for completing job i and profit pi (pi ≥ 0).

Only one job can be scheduled at a time, and each job takes exactly 1 unit of time. You earn profit for a job only if you complete it before or on its deadline. The task is to find the subset of jobs that maximises the total profit while adhering to deadlines.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

Input:
deadline = [4, 1, 1, 1]
profit   = [20, 10, 40, 30]

Output:
Maximum profit sequence of jobs: [2, 0]

Explanation:
- Job 2 (profit = 40, deadline = 1) is scheduled first (time = 1).
- Job 0 (profit = 20, deadline = 4) is scheduled next (time = 2).
- This results in a total profit of 40 + 20 = 60.

Example 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

Input:
deadline = [2, 1, 2, 1, 3]
profit   = [100, 19, 27, 25, 15]

Output:
Maximum profit sequence of jobs: [0, 2, 4]

Explanation:
- Job 0 (profit = 100, deadline = 2) is scheduled first (time = 1).
- Job 2 (profit = 27, deadline = 2) is scheduled next (time = 2).
- Job 4 (profit = 15, deadline = 3) is scheduled last (time = 3).
- This results in a total profit of 100 + 27 + 15 = 142.

Solution

Method 1 - Sorting + Greedy

Reasoning/intuition

  • To maximise profit, prioritise jobs with higher profits. Hence, sort the jobs in descending order of profit.
  • Use a greedy approach to schedule the highest-profit jobs first, checking the latest available timeslots (near to their deadlines).
  • Keep track of which timeslots are already booked.

Algorithm

  1. Combine the deadline and profit arrays into a single list of tuples (profit, deadline, index) for easier handling.
  2. Sort this list by profit in descending order.
  3. Find the maximum deadline to create a scheduling array.
  4. Use slots (timing) for job scheduling, where you choose the latest available slot for each job and maximise profits greedily.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

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

class Solution {
public:
    vector<int> jobScheduling(vector<int>& deadlines, vector<int>& profits) {
        int n = deadlines.size();
        vector<tuple<int, int, int>> jobs; // {profit, deadline, index}
        
        for (int i = 0; i < n; i++) {
            jobs.push_back({profits[i], deadlines[i], i});
        }
        
        // Sort jobs by profit in descending order
        sort(jobs.rbegin(), jobs.rend());
        
        int maxDeadline = *max_element(deadlines.begin(), deadlines.end());
        vector<int> slots(maxDeadline + 1, -1); // Slot availability
        vector<int> result; // Job indices to return
        
        // Schedule jobs
        for (auto& [profit, deadline, index] : jobs) {
            for (int t = min(maxDeadline, deadline); t > 0; t--) {
                if (slots[t] == -1) { // Free slot found
                    slots[t] = index;
                    result.push_back(index);
                    break;
                }
            }
        }
        return result;
    }
};

int main() {
    vector<int> deadlines = {4, 1, 1, 1};
    vector<int> profits = {20, 10, 40, 30};
    
    Solution s;
    vector<int> result = s.jobScheduling(deadlines, profits);
    cout << "Maximum profit sequence of jobs: ";
    for (auto& id : result) cout << id << " ";
    cout << endl;
    return 0;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

package main

import (
	"fmt"
	"sort"
)

type Job struct {
	Profit   int
	Deadline int
	Index    int
}

func jobScheduling(deadlines []int, profits []int) []int {
	n := len(deadlines)
	jobs := make([]Job, n)
	
	// Combine profits and deadlines into a slice of Jobs
	for i := 0; i < n; i++ {
		jobs[i] = Job{Profit: profits[i], Deadline: deadlines[i], Index: i}
	}
	
	// Sort jobs by descending profit
	sort.Slice(jobs, func(i, j int) bool {
		return jobs[i].Profit > jobs[j].Profit
	})
	
	maxDeadline := 0
	for _, job := range deadlines {
		if job > maxDeadline {
			maxDeadline = job
		}
	}
	
	slots := make([]int, maxDeadline+1)
	for i := range slots {
		slots[i] = -1
	}
	
	result := []int{}
	
	// Schedule jobs
	for _, job := range jobs {
		for t := min(maxDeadline, job.Deadline); t > 0; t-- {
			if slots[t] == -1 { // Free slot found
				slots[t] = job.Index
				result = append(result, job.Index)
				break
			}
		}
	}
	return result
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func main() {
	deadlines := []int{4, 1, 1, 1}
	profits := []int{20, 10, 40, 30}
	fmt.Println("Maximum profit sequence of jobs:", jobScheduling(deadlines, profits))
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

class Solution {
    public List<Integer> jobScheduling(int[] deadlines, int[] profits) {
        int n = deadlines.length;
        List<int[]> jobs = new ArrayList<>(); // {profit, deadline, index}
        
        for (int i = 0; i < n; i++) {
            jobs.add(new int[]{profits[i], deadlines[i], i});
        }
        
        // Sort jobs by profit in descending order
        Collections.sort(jobs, (a, b) -> b[0] - a[0]);
        
        int maxDeadline = Arrays.stream(deadlines).max().getAsInt();
        boolean[] slots = new boolean[maxDeadline + 1];
        List<Integer> result = new ArrayList<>();
        
        for (int[] job : jobs) {
            int profit = job[0], deadline = job[1], index = job[2];
            for (int t = Math.min(deadline, maxDeadline); t > 0; t--) {
                if (!slots[t]) { // Free slot found
                    slots[t] = true;
                    result.add(index);
                    break;
                }
            }
        }
        return result;
    }
    
    public static void main(String[] args) {
        int[] deadlines = {4, 1, 1, 1};
        int[] profits = {20, 10, 40, 30};
        
        Solution s = new Solution();
        System.out.println("Maximum profit sequence of jobs: " + s.jobScheduling(deadlines, profits));
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

class Solution {
    fun jobScheduling(deadlines: IntArray, profits: IntArray): List<Int> {
        val n = deadlines.size
        val jobs = mutableListOf<Job>()
        
        // Combine profits and deadlines into a list of Jobs
        for (i in 0 until n) {
            jobs.add(Job(profit = profits[i], deadline = deadlines[i], index = i))
        }
        
        // Sort jobs by descending profit
        jobs.sortByDescending { it.profit }
        
        val maxDeadline = deadlines.maxOrNull() ?: 0
        val slots = IntArray(maxDeadline + 1) { -1 } // Slot availability
        val result = mutableListOf<Int>()           // Result job indices
        
        // Schedule jobs
        for (job in jobs) {
            for (t in minOf(maxDeadline, job.deadline) downTo 1) {
                if (slots[t] == -1) { // Free slot found
                    slots[t] = job.index
                    result.add(job.index)
                    break
                }
            }
        }
        
        return result
    }
}

fun main() {
    val deadlines = intArrayOf(4, 1, 1, 1)
    val profits = intArrayOf(20, 10, 40, 30)
    
    val solution = Solution()
    println("Maximum profit sequence of jobs: ${solution.jobScheduling(deadlines, profits)}")
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution:
    def jobScheduling(self, deadlines, profits):
        # Combine job information into one list: (profit, deadline, index)
        jobs = [(profits[i], deadlines[i], i) for i in range(len(profits))]
        
        # Sort jobs by descending profit
        jobs.sort(reverse=True, key=lambda x: x[0])
        
        max_deadline = max(deadlines)
        slots = [-1] * (max_deadline + 1)
        result = []
        
        for profit, deadline, index in jobs:
            for t in range(min(deadline, max_deadline), 0, -1):
                if slots[t] == -1:  # Free slot found
                    slots[t] = index
                    result.append(index)
                    break
        return result

# Example
deadlines = [4, 1, 1, 1]
profits = [20, 10, 40, 30]
s = Solution()
print("Maximum profit sequence of jobs:", s.jobScheduling(deadlines, profits))
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

use std::cmp;

#[derive(Debug)]
struct Job {
    profit: i32,
    deadline: usize,
    index: usize,
}

struct Solution;

impl Solution {
    pub fn job_scheduling(deadlines: Vec<usize>, profits: Vec<i32>) -> Vec<usize> {
        let n = deadlines.len();
        let mut jobs: Vec<Job> = Vec::new();
        
        // Combine profits and deadlines into a list of Jobs
        for i in 0..n {
            jobs.push(Job {
                profit: profits[i],
                deadline: deadlines[i],
                index: i,
            });
        }
        
        // Sort jobs by descending profit
        jobs.sort_by(|a, b| b.profit.cmp(&a.profit));
        
        let max_deadline = deadlines.iter().copied().max().unwrap_or(0);
        let mut slots = vec![-1; max_deadline + 1]; // Slot availability
        let mut result = Vec::new();              // Result job indices
        
        // Schedule jobs
        for job in jobs {
            for t in (1..=cmp::min(max_deadline, job.deadline)).rev() {
                if slots[t] == -1 {
                    slots[t] = job.index as i32;
                    result.push(job.index);
                    break;
                }
            }
        }
        
        result
    }
}

fn main() {
    let deadlines = vec![4, 1, 1, 1];
    let profits = vec![20, 10, 40, 30];
    
    let result = Solution::job_scheduling(deadlines, profits);
    println!("Maximum profit sequence of jobs: {:?}", result);
}

Complexity

  • ⏰ Time complexity: O(n log n + n * d) for n jobs and max deadline as d
    • Sorting the jobs: O(n * log(n)).
    • For each job, checking available slots: O(n * d) where d is the maximum deadline.
    • Overall: O(n * log(n) + n * d).
  • 🧺 Space complexity: O(n + d). For storing the job list (input) and scheduling array: O(n + d).

Method 2 - Using disjoint set

Reasoning

  • Since each job has a fixed deadline, we aim to execute it before or at its deadline. Once a time slot t is used, we need to find the next available free time slot t-1 for scheduling.
  • Using disjoint sets, we can dynamically and efficiently track the parent (next available slot) for the time slots.

Steps

  1. Sort jobs by profit:

    • Arrange all jobs in descending order of profit. This ensures we always prioritise the jobs with the highest profit while scheduling.

  2. Find the maximum deadline d_max:

    • Determine the maximum deadline of any job. This allows us to restrict our search space for available time slots to the range [1, d_max].

  3. Create disjoint sets:

    • Initialise a disjoint set array, where each index represents a time slot, and its value points to the next available slot. Initially: parent[i] = i (each slot points to itself initially)

  4. Process each job:

    • Iterate through the sorted jobs (highest-profit first). For each job:
      • Find the maximum available time slot ≤ the job’s deadline using the Find operation of the disjoint set.
      • If a slot is available:
        • Schedule the job in that slot.
        • Update the parent of the current slot to point to its previous slot (t-1) using the Union operation. This ensures the next time slot for future jobs is correctly tracked.

Key Intuition of Disjoint Set Operations

  • Find operation:

    • For a given slot, the Find operation helps locate the farthest available time up to that slot (e.g., if slot 5 is occupied, it points to 4). This prevents unnecessary linear scans for available times.

  • Union operation:

    • When a slot t is occupied, we “union” it with t-1 to specify that t is no longer independent and refers to the next available slot (t-1).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

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

class Solution {
public:
    // Find operation for Disjoint Set with path compression
    int find(vector<int>& parent, int x) {
        if (parent[x] == x) {
            return x;
        }
        return parent[x] = find(parent, parent[x]); // Path compression
    }

    // Union operation for Disjoint Set
    void unionSet(vector<int>& parent, int x, int y) {
        parent[x] = y; // Merge x into y
    }

    vector<int> jobScheduling(vector<int>& deadlines, vector<int>& profits) {
        int n = deadlines.size();
        vector<tuple<int, int, int>> jobs; // {profit, deadline, index}

        // Step 1: Combine job information into one list
        for (int i = 0; i < n; i++) {
            jobs.push_back({profits[i], deadlines[i], i});
        }
        
        // Step 2: Sort jobs by descending profit
        sort(jobs.rbegin(), jobs.rend());
        
        // Step 3: Find the maximum deadline
        int maxDeadline = *max_element(deadlines.begin(), deadlines.end());
        
        // Step 4: Initialize disjoint set
        vector<int> parent(maxDeadline + 1);
        for (int i = 0; i <= maxDeadline; i++) {
            parent[i] = i; // Each slot points to itself initially
        }
        
        // Step 5: Process each job
        vector<int> result;
        for (auto& [profit, deadline, index] : jobs) {
            // Find the latest available time slot (≤ deadline)
            int availableSlot = find(parent, deadline);
            if (availableSlot > 0) { // If slot is available
                result.push_back(index); // Schedule job
                unionSet(parent, availableSlot, find(parent, availableSlot - 1)); // Merge the slot
            }
        }
        
        return result;
    }
};

int main() {
    vector<int> deadlines = {4, 1, 1, 1};
    vector<int> profits = {20, 10, 40, 30};

    Solution s;
    vector<int> result = s.jobScheduling(deadlines, profits);
    cout << "Maximum profit sequence of jobs: ";
    for (auto id : result) {
        cout << id << " ";
    }
    cout << endl;

    return 0;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

class Solution {
    // Find operation for Disjoint Set
    private int find(int[] parent, int x) {
        if (parent[x] == x) {
            return x;
        }
        return parent[x] = find(parent, parent[x]); // Path compression
    }

    // Union operation for Disjoint Set
    private void union(int[] parent, int x, int y) {
        parent[x] = y; // Union (link x to y)
    }

    public List<Integer> jobScheduling(int[] deadlines, int[] profits) {
        int n = deadlines.length;

        // Combine job information in (profit, deadline, index) format
        List<int[]> jobs = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            jobs.add(new int[]{profits[i], deadlines[i], i});
        }

        // Step 1: Sort jobs by descending profit
        jobs.sort((a, b) -> b[0] - a[0]);

        // Step 2: Find the maximum deadline
        int maxDeadline = Arrays.stream(deadlines).max().getAsInt();

        // Step 3: Initialize disjoint set
        int[] parent = new int[maxDeadline + 1];
        for (int i = 0; i <= maxDeadline; i++) {
            parent[i] = i; // Each slot points to itself initially
        }

        // Step 4: Process each job
        List<Integer> result = new ArrayList<>();
        for (int[] job : jobs) {
            int profit = job[0], deadline = job[1], index = job[2];

            // Find the latest available time slot (≤ deadline)
            int availableSlot = find(parent, deadline);
            if (availableSlot > 0) { // If slot is available
                result.add(index); // Schedule job
                union(parent, availableSlot, find(parent, availableSlot - 1)); // Merge the slot
            }
        }

        return result;
    }

    public static void main(String[] args) {
        int[] deadlines = {4, 1, 1, 1};
        int[] profits = {20, 10, 40, 30};

        Solution s = new Solution();
        System.out.println("Maximum profit sequence of jobs: " + s.jobScheduling(deadlines, profits));
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

class Solution:
    def find(self, parent, x):
        # Find operation with path compression
        if parent[x] != x:
            parent[x] = self.find(parent, parent[x])
        return parent[x]

    def union(self, parent, x, y):
        # Union operation
        parent[x] = y

    def jobScheduling(self, deadlines, profits):
        n = len(deadlines)
        
        # Combine job information as (profit, deadline, index)
        jobs = [(profits[i], deadlines[i], i) for i in range(n)]
        
        # Step 1: Sort jobs by descending profit
        jobs.sort(reverse=True, key=lambda x: x[0])
        
        # Step 2: Find the maximum deadline
        max_deadline = max(deadlines)
        
        # Step 3: Initialize disjoint set
        parent = [i for i in range(max_deadline + 1)]
        
        # Step 4: Process each job
        result = []
        for profit, deadline, index in jobs:
            # Find the latest available time slot (≤ deadline)
            available_slot = self.find(parent, deadline)
            if available_slot > 0:  # If slot is available
                result.append(index)  # Schedule job
                self.union(parent, available_slot, self.find(parent, available_slot - 1))  # Merge the slot
        
        return result

# Example usage
deadlines = [4, 1, 1, 1]
profits = [20, 10, 40, 30]

s = Solution()
print("Maximum profit sequence of jobs:", s.jobScheduling(deadlines, profits))

Complexity

  • ⏰ Time complexity: O(n log n)
    • Sorting the jobs by profit (descending) takes O(n * log(n)).
    • Disjoint Set Operations:
      • The Find and Union operations both have an amortised time complexity of O(α(n)), where α(n) is the inverse Ackermann function, which grows very slowly (effectively constant for most practical purposes).
      • Each job involves one Find and one Union operation. For n jobs, this amounts to O(n) disjoint set operations in total.
  • 🧺 Space complexity: O(n + d_max)
    • Disjoint set array for d_max time slots: O(d_max).
    • Storage for jobs: O(n).