We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
- Prepare
- Algorithms
- Greedy
- Luck Balance
- Discussions
Luck Balance
Luck Balance
Sort by
recency
|
930 Discussions
|
Please Login in order to post a comment
Here is my intuition for solving this problem:
Lena is ultimately trying to maximize her luck. We have a list of contests along with their luck and whether they are important or not. In a perfect world she would just bank as much luck as possible and lose every contest, but there is a constraint that stops her from doing this. You can only lose k important contests. So I thought of k as special tokens that I can spend. So for each contest you have 3 scenarios:
Lena wants to maximize her luck, so if she spends a special token, it better be worth it. In other words be greedy and only spend tokens on the contests that will get you the most luck. With this as a guide you can sort the contests by luck in descending order, then pick the contests that will get you the most luck while spending special tokens. Because the contests are sorted by luck, when you spend a special token (k-= 1) on a contest i, you can be sure that there is no other contest that you can spend a special token on, that will get you more luck or else it would occur before contest i in the array, meaning that you have the optimal solution.
Running Time:
Because O(n) is bounded above by O(n log n) the running time of this algorithm is O(n log n)
Python Solution:
public static int luckBalance(int k, List> contests) { PriorityQueue que = new PriorityQueue<>(); // min-heap int sum = 0;
Here is my c++ solution, you can watch the explanation here : https://youtu.be/7L1lI6JScR8