# Question
You are given a set of N jobs where each job comes with a deadline and profit. The profit can only be earned upon completing the job within its deadline. Find the number of jobs done and the maximum profit that can be obtained. Each job takes a single unit of time and only one job can be performed at a time.

# Intuition
Sort jobs by deadline and greedily keep the most profitable set that fits deadlines. Use a min-heap of selected job profits: push a profit when the number of selected jobs is less than the current job's deadline; otherwise, if the current profit is larger than the smallest selected profit, replace it. The heap always contains the best profits for available slots.

# Approach
1. Pair deadlines and profits.
2. Sort pairs by deadline (ascending).
3. Use a min-heap to store chosen job profits:
        - If heap.size() < deadline, push profit.
        - Else if profit > heap.top(), pop and push profit.
4. Sum heap values and count jobs.

# Complexity
- Time complexity: O(n log n) — sorting takes O(n log n) and each heap operation is O(log n).
- Space complexity: O(n) — for pairs and heap.

# Code
```cpp []
class Solution {
  public:
      vector<int> jobSequencing(vector<int> &deadline, vector<int> &profit) {
        
        int n = deadline.size();
        vector<int> ans = {0, 0};
        vector<pair<int, int>> jobs;
        for (int i = 0; i < n; i++) {
            jobs.push_back({deadline[i], profit[i]});
        }
    
        // sort the jobs based on deadline
        // in ascending order
        sort(jobs.begin(), jobs.end());
        priority_queue<int, vector<int>, greater<int>> pq;
    
        for (int i = 0; i < jobs.size(); i++) {
            
            // if job can be scheduled within its deadline
            if (jobs[i].first > pq.size())
                pq.push(jobs[i].second);
            
            // replace the job with the lowest profit
            else if (!pq.empty() && pq.top() < jobs[i].second) {
                pq.pop();
                pq.push(jobs[i].second);
            }
        }
    
        while (!pq.empty()) {
            ans[1] += pq.top();
            pq.pop();
            ans[0]++;
        }
    
        return ans;
    }
};



```


```python []
import heapq
from typing import List

def job_sequencing(deadline: List[int], profit: List[int]) -> List[int]:
         jobs = list(zip(deadline, profit))
         jobs.sort(key=lambda x: x[0])  # sort by deadline
         pq = []  # min-heap of chosen profits

         for d, p in jobs:
                  if len(pq) < d:
                                heapq.heappush(pq, p)
                  elif pq and pq[0] < p:
                                heapq.heapreplace(pq, p)

         total_profit = sum(pq)
         return [len(pq), total_profit]
```


```java []
import java.util.*;

class Solution {
         public int[] jobSequencing(int[] deadline, int[] profit) {
                  int n = deadline.length;
                  int[] ans = new int[]{0, 0};
                  List<int[]> jobs = new ArrayList<>();
                  for (int i = 0; i < n; ++i) jobs.add(new int[]{deadline[i], profit[i]});
                  jobs.sort(Comparator.comparingInt(a -> a[0]));

                  PriorityQueue<Integer> pq = new PriorityQueue<>(); // min-heap
                  for (int[] job : jobs) {
                                int d = job[0], p = job[1];
                                if (pq.size() < d) pq.add(p);
                                else if (!pq.isEmpty() && pq.peek() < p) {
                                         pq.poll();
                                         pq.add(p);
                                }
                  }

                  while (!pq.isEmpty()) {
                                ans[1] += pq.poll();
                                ans[0]++;
                  }
                  return ans;
         }
}
```


```javascript []
// Minimal min-heap implementation
class MinHeap {
  constructor() { this.a = []; }
  size() { return this.a.length; }
  peek() { return this.a[0]; }
  push(val) {
         this.a.push(val);
         let i = this.a.length - 1;
         while (i > 0) {
                let p = Math.floor((i - 1) / 2);
                if (this.a[p] <= this.a[i]) break;
                [this.a[p], this.a[i]] = [this.a[i], this.a[p]];
                i = p;
         }
  }
  pop() {
         if (this.a.length === 0) return undefined;
         const ret = this.a[0];
         const last = this.a.pop();
         if (this.a.length) {
                this.a[0] = last;
                let i = 0;
                while (true) {
                  let l = 2 * i + 1, r = 2 * i + 2, smallest = i;
                  if (l < this.a.length && this.a[l] < this.a[smallest]) smallest = l;
                  if (r < this.a.length && this.a[r] < this.a[smallest]) smallest = r;
                  if (smallest === i) break;
                  [this.a[i], this.a[smallest]] = [this.a[smallest], this.a[i]];
                  i = smallest;
                }
         }
         return ret;
  }
}

function jobSequencing(deadline, profit) {
  const jobs = deadline.map((d, i) => [d, profit[i]]);
  jobs.sort((a, b) => a[0] - b[0]);
  const pq = new MinHeap();

  for (const [d, p] of jobs) {
         if (pq.size() < d) pq.push(p);
         else if (pq.size() && pq.peek() < p) {
                pq.pop();
                pq.push(p);
         }
  }

  let total = 0, count = 0;
  while (pq.size()) {
         total += pq.pop();
         count++;
  }
  return [count, total];
}
```



QuestionYou are given a set of N jobs where each job comes with a deadline and profit. The profit can only be earned upon completing the job within its deadline. Find the number of jobs done and the maximum profit that can be obtained. Each job takes