(GREEDY) Job Sequencing Problem

Similar to expiry of products
 avatar
unknown
java
15 days ago
1.5 kB
5
Indexable
class Pair{
    int start;
    int end;
    
    Pair(int start, int end)
    {
        this.start = start;
        this.end = end;
    }
}
class Solution {

    public ArrayList<Integer> JobSequencing(int[] id, int[] deadline, int[] profit) {
        int i, n = deadline.length;
        Pair[] pairs = new Pair[n];
        for(i=0;i<n;++i)
        {
            pairs[i] = new Pair(deadline[i], profit[i]);
        }
        
        Arrays.sort(pairs, Comparator.comparingInt(p -> p.start));
        
        for(i=0;i<n;++i)
        {
            deadline[i] = pairs[i].start;
            profit[i] = pairs[i].end;
        }
        
        int t = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
        ArrayList<Integer> arr = new ArrayList<Integer>();
        for(i=0;i<n;++i)
        {
            if(t<deadline[i])
            {
                t++;
                pq.add(profit[i]);
            }
            else
            {
                int minProfit = pq.peek();
                if(minProfit < profit[i])
                {
                    pq.poll();
                    pq.add(profit[i]);
                }
            }
            System.out.println("top "+ pq.peek());
        }
        
        int ans = 0;
        for(i=0;i<pq.size();++i)
        {
            ans += pq.peek();
            pq.poll();
        }
        
        arr.add(pq.size());
        arr.add(ans);
        return arr;
    }
}
Editor is loading...
Leave a Comment