• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Untitled

a guest Sep 18th, 2019 85 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. def get_damages(H):
2.     '''
3.     Input:  H | list of bricks per house from west to east
4.     Output: D | list of damage per house from west to east
5.     '''
6.     D = [1 for _ in H]
7.     ##################
8.     # YOUR CODE HERE #
9.     ##################
10.     house_orderer = [[house, index, 1] for index, house in enumerate(H)]
11.
12.     def helper(A, low=0, high=None):
13.         if high is None:
14.             high = len(A)-1
15.         if 1 < high - low:
16.             mid = (low + high + 1) // 2
17.             # Sort sublists
18.             helper(A, low, mid)
19.             helper(A, mid, high)
20.
21.             # Merge process starts here
22.             L, R = A[low:mid], A[mid:high]
23.             i, j = len(L)-1,len(R)-1
24.
25.             # Check to see damages for each house, and add values to damage array
26.             while i >= 0 and j>=0:
27.                 if L[i] > R[j]:
28.                     L[i][2] += len(R[:j+1])
29.                     A[high] = L[i]
30.                     i -= 1
31.                 else:
32.                     A[high] = R[j]
33.                     j -= 1
34.             while i >= 0:
35.                 A[high] = L[i]
36.                 i -=1
37.                 high -= 1
38.             while j >= 0:
39.                 A[high] = R[j]
40.                 j -=1
41.                 high -=1
42.
43.             # while low < high:
44.             #     if (j >= len(R)) or (i < len(L) and L[i][0] < R[j][0]):
45.             #         A[low] = L[i]
46.             #         i += 1
47.             #     else:
48.             #         A[low] = R[j]
49.             #         D[i] += len(R[:j])
50.             #         j += 1
51.             #     low += 1
52.
53.     helper(house_orderer)
54.     print(house_orderer)
55.     print(D)
56.     return D
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.
Not a member of Pastebin yet?