Job Sequencing Problem

ERROR


class Solution {
  public:
    struct Comparator{
        
        bool operator()(pair<int,int> a,pair<int,int> b){
            
            if(a.first==b.first)
                a.second<  b.second;
            
            return a<b;
            
        }
    };
  
    vector<int> jobSequencing(vector<int> &deadline, vector<int> &profit) {
        // code here
        
        vector<pair<int,int>> v;
        for(int i=0;i<deadline.size();i++){
            v.push_back({profit[i],deadline[i]});
        }
        
        sort(v.begin,v.end(),Comparator());
        
        int time=0;
        
        int totalProfit=0;
        int totalJobs=0;
        for(int i=0;i<v.size();i++){
            
            // within deadline
            if(time>=v[i][1]){
                totalProfit+=v[i][0];
                totalJobs++;
            }
            
            time++;
            
        }
        
        return {totalJobs,totalProfit};
        
    }
};



// sort by end time
// ,and try to finish a smany jobs as poosible



// in these type of scenarios


// there are 2 poosibilties

// 1.finish as many jobs as possible, and make profits


// or sort by profits


// so ill sort by profits, if prfots are same sort by time interval


// because if we finish the lest deadline one first, then we can take later deadline ones later


// Eg : [2,1,2,1,1]
// profot =  [100, 19, 27, 25, 15]


// [{100,2},{27,2},{25,1},{19,1},{15,1}]



// time =1

// 100,2 -   i can finish because it will take 1 unit to finsh the time
//           and deadline is 2 , so ill finish
          

// time=2
// 27,2 -  I can finish.

// time - 3
// 25,1 - cant finish

_____________________________


SOLUTION : 

//      Some jobs with later deadlines can be placed in earlier time slots (if those are still free).
// Your current approach can't handle that at all — because you're not tracking what slots are filled.     


How It Should Work:
You need to track which slots (days) are available for scheduling.





class Solution {
public:
    struct Comparator {
        bool operator()(pair<int, int>& a, pair<int, int>& b) {
            return a.first > b.first; // Sort by profit descending
        }
    };

    vector<int> jobSequencing(vector<int>& deadline, vector<int>& profit) {
        int n = deadline.size();
        vector<pair<int, int>> jobs;

        // Step 1: Pair profit with deadline
        for (int i = 0; i < n; i++) {
            jobs.push_back({profit[i], deadline[i]});
        }

        // Step 2: Sort by profit descending
        sort(jobs.begin(), jobs.end(), Comparator());

        // Step 3: Find max deadline to know how many slots we need
        int maxDeadline = *max_element(deadline.begin(), deadline.end());
        
        
        vector<bool> slot(maxDeadline + 1, false); // slot[1..maxDeadline]



        int totalJobs = 0, totalProfit = 0;

        // Step 4: Schedule each job in the latest available time before its deadline
        for (auto& job : jobs) {
            
            int d = job.second; // deadline
            
            
            // fill this job in whichver slot is empty
            // start filling from end - end means - not the end ,
            // from the deadline of the project
            
            // eg:lets say maxDealine - 6
            // but my curr project deadline - 3 -  tht means it can be worked 
            // on 1/2/3
            // so I need to start from 3rd slot onwards, lets say 3rd slot is filled, check, 2nd
            // then check 1st....., until we find any empty slot.
            
            
            
            // WHy from end?
            // Why not strat filling from 1....maxDealine
            
            // because lets say first project  deadline was 3
            // and 1st slot is free and i filled this project
            // next project deadline was 1, but i is filled and i can tit...
            // so fill from max time we could get
            
            
            // why start filling from end, 
            for (int t = d; t >= 1; t--) {
                
                if (!slot[t]) {
                    
                    slot[t] = true; // Mark slot as used
                    totalJobs++;
                    totalProfit += job.first;
                    break;
                }
            }
        }

        return {totalJobs, totalProfit};
    }
};




_____________________________




DSU  : 

profit =  [100, 90, 80]
deadline = [3, 2, 1]


Processing Job 1 (deadline 3):

Edit
int avail = find(3); // What is the latest free slot ≤ 3?

find(3):
    parent[3] = 3 → it's free
So we schedule it at time 3.

Now time 3 is used → update DSU:

merge(3, 2); // means: now the latest free slot ≤ 3 is 2
So:

parent[3] = 2


_________


Processing Job 2 (deadline 2):

int avail = find(2);

find(2):
    parent[2] = 2 → it's free
We schedule it at time 2.

Update DSU:
merge(2, 1); → parent[2] = 1


_______

Processing Job 3 (deadline 1):


int avail = find(1);

find(1):
    parent[1] = 1 → it's free
We schedule it at time 1.

Update DSU:

merge(1, 0); → parent[1] = 0


❌ Now all time slots are used
If a new job comes with deadline = 3:


int avail = find(3);
It will check:

parent[3] = 2

parent[2] = 1

parent[1] = 0 ← No available slot

So avail = 0 → we skip the job.

_____________



class Solution {
public:
    struct Comparator {
        bool operator()(pair<int, int>& a, pair<int, int>& b) {
            return a.first > b.first; // Sort by profit descending
        }
    };

    vector<int> parent;

    // DSU find with path compression
    
//     parent[i] means the latest free time slot ≤ i.

// Initially: parent[i] = i (i.e., all time slots are free).
    int find(int x) {
        if (parent[x] == x) return x;
        return parent[x] = find(parent[x]);
    }



    // DSU union
    void merge(int u, int v) {
        parent[u] = v;
    }
    
    

    vector<int> jobSequencing(vector<int>& deadline, vector<int>& profit) {
        int n = deadline.size();
        vector<pair<int, int>> jobs;

        for (int i = 0; i < n; i++) {
            jobs.push_back({profit[i], deadline[i]});
        }

        // Sort by descending profit
        sort(jobs.begin(), jobs.end(), Comparator());

        // Find max deadline
        int maxDeadline = *max_element(deadline.begin(), deadline.end());




        // DSU parent initialization
        parent.resize(maxDeadline + 1);
        for (int i = 0; i <= maxDeadline; i++) parent[i] = i;
        
        

        int totalProfit = 0, totalJobs = 0;

        for (auto& job : jobs) {
           
           
           
        //   THIS iS the key here  , find the before slot which is free and merge those,both
            int avail = find(job.second); // Find latest available slot ≤ deadline
            
           
            if (avail > 0) {
                totalProfit += job.first;
                totalJobs++;
                
                
                // merge is imp
                merge(avail, avail - 1); // Mark this slot as used
            }
            
            
        }

        return {totalJobs, totalProfit};
    }
};




// Now suppose:

// Job1 has deadline 4 → find(4) returns 4, assign it there.

// Mark 4 as used → redirect parent[4] = 3

// Job2 has deadline 4 → find(4) → finds 3, assign it → redirect parent[3] = 2

// Job3 has deadline 2 → find(2) → gets 2, assign → parent[2] = 1

// Now if another job comes with deadline 4:


// find(4) → 3 → 2 → 1 → available!