-
Notifications
You must be signed in to change notification settings - Fork 0
/
climbing_the_leaderboard.py
60 lines (41 loc) · 1.21 KB
/
climbing_the_leaderboard.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
# Solution 1 - Linear Search
num_ranks = int(input())
ranks = list(map(int, input().split()))
num_scores = int(input())
scores = list(map(int, input().split()))
unique_ranks = sorted(set(ranks))
len_unique_ranks = len(unique_ranks)
i = 0
for score in scores:
while i < len_unique_ranks:
if score < unique_ranks[i]:
break
i += 1
print(len_unique_ranks+1-i)
# Solution 2 - Binary Search
def climbingLeaderboard(ranked, player):
ans = []
unique_ranks = sorted(set(ranked))
unique_ranks.reverse()
for i in player:
floor_idx = BS(i, unique_ranks)
ans.append(floor_idx+1)
for i in ans:
print(i)
def BS(i, ranked):
lo = 0
hi = len(ranked)-1
while lo <= hi:
mid = lo + (hi-lo)//2
if ranked[mid] > i:
lo = mid+1
else:
hi = mid -1
return lo
num_ranked = int(input())
ranked = list(map(int, input().split()))
num_player = int(input())
player = list(map(int, input().split()))
unique_ranked = sorted(set(ranked))
len_unique_ranked = len(unique_ranked)
climbingLeaderboard(ranked, player)