uopspop

Untitled

Jun 19th, 2021
792
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2.    
  3.     class Node {
  4.         double w_per_q;
  5.         Double quality;
  6.        
  7.         public Node(double w_per_q, Double quality) {
  8.             this.w_per_q = w_per_q;
  9.             this.quality = quality;
  10.         }
  11.        
  12.     }
  13.    
  14.     class MyCompByWageUnit implements Comparator<Node> {
  15.         public int compare(Node n1, Node n2) {
  16.             if (n1.w_per_q > n2.w_per_q) return 1;
  17.             else if (n1.w_per_q < n2.w_per_q) return -1;
  18.             else return 0;
  19.            
  20.         }
  21.     }
  22.    
  23.     class MyCompReverse implements Comparator<Double> {
  24.         public int compare(Double n1, Double n2) {
  25.             if (n1 > n2) return -1;
  26.             else if (n1 < n2) return +1;
  27.             else return 0;
  28.         }
  29.     }
  30.    
  31.     public double mincostToHireWorkers(int[] quality, int[] wage, int k) {
  32.         // n 數量級
  33.         // val 數字值大小
  34.        
  35.         // the basic unit pay will be decided by: max w/q
  36.         // result: min( (max w/q) * total_combined_q )
  37.        
  38.         // sort w/q - we intend to go from smallest w/q first to the largest
  39.         Node[] wage_units = new Node[wage.length];
  40.         for (int i = 0; i < quality.length ;i++) {
  41.             double q = quality[i];
  42.             double w = wage[i];
  43.             wage_units[i] = new Node(w/q, q);
  44.         }
  45.        
  46.         Arrays.sort(wage_units, new MyCompByWageUnit());
  47.        
  48.         // int count = 0;
  49.         Double result_min = Double.MAX_VALUE;
  50.         Double q_sum = 0d;
  51.         TreeSet<Double> set_quality_max = new TreeSet<>();
  52.         // PriorityQueue<Double> pq_quality_max = new PriorityQueue<>(100, new MyCompReverse());
  53.         for (int i = 0; i < wage_units.length ;i++) {
  54.            
  55.             if (i >= k) {
  56.                 // Double q_to_removed = pq_quality_max.poll();
  57.                 Double q_to_removed = set_quality_max.pollLast();
  58.                 q_sum -= q_to_removed; // attention: you need to maintian the top K elements
  59.             }
  60.            
  61.             Node node_now = wage_units[i];
  62.             Double wage_unit = node_now.w_per_q;
  63.             double quality_now = node_now.quality;
  64.             // pq_quality_max.offer(quality_now);
  65.             if (set_quality_max.contains(quality_now)) {
  66.                 System.out.println("you cannot use TreeSet cuz there is DUPLICATE!");
  67.             }
  68.             set_quality_max.add(quality_now);
  69.             q_sum += quality_now; // attention: you need to maintian the top K elements  
  70.                                   // attention: and the reason you don't have to pop K elements every time, is cuz you MUST add the i number since it has the max_wageUnit here in the leetcode question
  71.            
  72.             if (i >= k - 1) {
  73.                 // record result now
  74.                 result_min = Math.min(result_min, wage_unit * q_sum);
  75.             }
  76.            
  77.         } // end of if
  78.        
  79.         return result_min;  
  80.     }
  81.    
  82. }
RAW Paste Data