(GREEDY) Job Sequencing Problem
Similar to expiry of productsunknown
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