 # 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.             }
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