*29. Job Sequencing Problem**

The problem can be found at the following link: Question Link

Note: Sorry for uploading late, my exam is going on.

Problem Description

You are given two arrays: deadline[] and profit[], which represent a set of jobs. Each job:

• Has a deadline by which it must be completed.

• Has a profit associated with it.

• Takes exactly one unit of time to complete.

• Only one job can be scheduled at a time.

Your task is to determine:

1. The maximum number of jobs that can be completed within their deadlines.

2. The maximum total profit that can be earned by scheduling jobs optimally.

Examples

Example 1:

Input:

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

Output:

[2, 60]

Explanation:

Jobs 1 and 3 can be scheduled, maximizing profit (20 + 40 = 60).

Example 2:

Input:

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

Output:

[2, 127]

Explanation:

Jobs 1 and 3 can be scheduled, maximizing profit (100 + 27 = 127).

Example 3:

Input:

deadline = [3, 1, 2, 2]
profit = [50, 10, 20, 30]

Output:

[3, 100]

Explanation:

Jobs 1, 3, and 4 can be scheduled, maximizing profit (50 + 20 + 30 = 100).

Constraints

• $( 1 \leq \text{deadline.size()} == \text{profit.size()} \leq 10^5 )$

• $( 1 \leq \text{deadline}[i] \leq \text{deadline.size()} )$

• $( 1 \leq \text{profit}[i] \leq 500 )$

My Approach:

Greedy + Min Heap

Algorithm Steps:

1. Sort jobs in ascending order of deadlines (if two jobs have the same deadline, sort by profit).

2. Use a min heap to keep track of scheduled jobs based on their profits.

3. Iterate through jobs and schedule them:

   • If the number of scheduled jobs is less than the current job's deadline, add it to the heap.

   • If a lower-profit job exists in the heap, replace it with the current job.

4. Return the total jobs scheduled and the sum of profits from the heap.

Time and Auxiliary Space Complexity

• Expected Time Complexity: $( O(N \log N) )$, due to sorting and heap operations.

• Expected Auxiliary Space Complexity: $( O(N) )$, due to storing jobs in a heap.

Code (C++)

class Solution {
public:
    vector<int> jobSequencing(vector<int>& d, vector<int>& p) {
        vector<pair<int, int>> jobs;
        for (int i = 0; i < d.size(); ++i) jobs.emplace_back(d[i], p[i]);
        sort(jobs.begin(), jobs.end());

        priority_queue<int, vector<int>, greater<int>> pq;
        for (const auto& job : jobs) {
            if (job.first > pq.size()) pq.push(job.second);
            else if (pq.top() < job.second) pq.pop(), pq.push(job.second);
        }

        int cnt = pq.size(), tot = 0;
        while (!pq.empty()) tot += pq.top(), pq.pop();
        return {cnt, tot};
    }
};

Code (Java)

class Solution {
    public ArrayList<Integer> jobSequencing(int[] d, int[] p) {
        int n = d.length, cnt = 0, tot = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        List<int[]> jobs = new ArrayList<>();

        for (int i = 0; i < n; i++) jobs.add(new int[] {d[i], p[i]});
        jobs.sort(Comparator.comparingInt(a -> a[0]));

        for (int[] job : jobs) {
            if (job[0] > pq.size()) pq.add(job[1]);
            else if (pq.peek() < job[1]) { pq.poll(); pq.add(job[1]); }
        }

        cnt = pq.size();
        while (!pq.isEmpty()) tot += pq.poll();

        return new ArrayList<>(Arrays.asList(cnt, tot));
    }
}

Code (Python)

from heapq import heappush, heappop

class Solution:
    def jobSequencing(self, d, p):
        jobs = sorted(zip(d, p))
        pq = []

        for deadline, profit in jobs:
            if len(pq) < deadline:
                heappush(pq, profit)
            elif pq and pq[0] < profit:
                heappop(pq)
                heappush(pq, profit)

        return [len(pq), sum(pq)]

Contribution and Support

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: Any Questions. Let’s make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

---

📍Visitor Count