python3 class Solution: def visibleMountains(self, peaks: List[List[int]]) -> int: # sort peaks in ascending order of (x - y) x-intercept # and also in descending order of (x + y) x-intercept peaks.sort(key=lambda x: ((x[0] - x[1]), -(x[0] + x[1]))) count = 0 max_end = float('-inf') for i, (x, y) in enumerate(peaks): if x + y > max_end: max_end = x + y if i < len(peaks) - 1 and peaks[i] == peaks[i + 1]: continue count += 1 return count
@leelashreerajendran872610 ай бұрын
Brute force solution : #assume the widest base and tallest mountain max_x = input[0][0] max_y = input[0][1] #calculate the widest base and tallest mountain for i in input: left_base = i[0]-i[1] right_base = i[0]+i[1] max_x = max(max_x, left_base) max_y = max(max_y, i[1]) #generate a 2D map of the scenery scenery = [[0 for i in range(max_y+1)] for j in range(-1*max_x, max_x + 1)] #populate the overlapping mountains for i in input: scenery[i[0]][i[1]] += 1 temp_y = i[1] - 1 counter = 1 while (temp_y > 0): for j in range(counter): scenery[i[0]-j][temp_y] += 1 scenery[i[0]+j][temp_y] += 1 counter += 1 temp_y -= 1 #Find the peaks which are not overlapped visible_mountain = 0 for i in input: if scenery[i[0]][i[1]] == 1: visible_mountain += 1 print(visible_mountain)