You are given games, a list of game entries, where every entry is a two-item list of strings. The first string is the score as an integer, and the second string is the result: either "win" or "lose". You are also given a decimal threshold in the range [0, 1] that specifies the minimum required proportion of losses.
Find the smallest non-negative integer s such that, when you consider only the entries whose score is at least s, the proportion of those entries with result "lose" is greater than or equal to threshold.
s does not have to be one of the scores present in the input.s can meet the condition, return -1.0.Keep in mind that the dataset may contain thousands of records, so an efficient method for identifying s is expected.
Constraints:
1 <= games.length <= 10^5games[i][0] is a string representation of a non-negative integer from 0 to 10^9.games[i][1] is either "win" or "lose".0 <= threshold <= 1Example 1:
games = [["40", "lose"], ["20", "win"], ["50", "lose"], ["30", "win"], ["40", "lose"]], threshold = 0.65
21
Among the entries with score at least 21, the games are [["40", "lose"], ["50", "lose"], ["30", "win"], ["40", "lose"]]. Three of these four are losses, which is 75%. That satisfies the required 65%. Lowering the cutoff below 21 would add the 20-score win and reduce the loss ratio, while any cutoff from 21 through 30 selects the same set, so 21 is the smallest valid answer.
Example 2:
games = [["10", "lose"], ["20", "lose"]], threshold = 0.5
0
A cutoff of 0 includes both games; both are losses, so the loss ratio is 100%, meeting the 50% requirement.
Example 3:
games = [["10", "win"], ["20", "win"]], threshold = 0.5
-1
Every game is a win, so no cutoff can produce a set whose loss ratio is at least 50%.
Example 1
Input:
5
40 lose
20 win
50 lose
30 win
40 lose
0.65
Output: 21
Example 2
Input:
2
10 lose
20 lose
0.5
Output: 0