I am trying to solve the [skyline problem][1] using the divide and conquer approach. For some inputs (attached) the program goes into infinite loop, but some other inputs it is working correctly. I have tried to print the skyline comparisons for each iteration but still could not figure it out why the program is not stopping. The input format is (x1, height, x2). x1-left point of the building, x2-rightmost point of the building, h-height. The output will be list of doubles representing the skylines.
def get_input():
# buildings = []
with open('test.txt') as file:
buildings = []
for line in file:
building = [int(point) for point in line.strip().split()]
buildings.append(building)
# print(buildings)
return buildings
def can_append(skyline, current_pos):
# print(skyline, "||||", current_pos)
# input("press")
last_skl_size = len(skyline)
if last_skl_size > 0 and skyline[last_skl_size-1][1] == current_pos[1]:
# print(skyline[last_skl_size-1], current_pos)
# input("press")
return
if last_skl_size > 0 and skyline[last_skl_size-1][0] == current_pos[0]:
skyline[last_skl_size-1][1] = max(skyline[last_skl_size-1][1], current_pos[1])
# print(skyline[last_skl_size-1], current_pos)
# input("press")
return
skyline.append(current_pos)
def merge_skylines(skyline_low, skyline_high):
skyline = []
low_len = len(skyline_low)
high_len = len(skyline_high)
# print(skyline_low)
h1, h2 = 0, 0 # Current height of skyline_low and skyline_high
h = 0 # Final height
i, j = 0, 0 # Current indices of the separate skylines
# print(skyline_low, skyline_high)
while (i < len(skyline_low) and j < len(skyline_high)):
if skyline_low[i][0] < skyline_high[j][0]:
h1 = skyline_low[i][1]
h = max(h1, h2)
can_append(skyline, [skyline_low[i][0], h])
# skyline.append([skyline_low[i][0], h])
i += 1
elif skyline_low[i][0] > skyline_high[j][0]:
h2 = skyline_high[j][1]
h = max(h1, h2)
can_append(skyline, [skyline_high[j][0], h])
# skyline.append([skyline_high[j][0], h])
j += 1
else:
h1 = skyline_low[i][1]
h2 = skyline_high[j][1]
h = max(h1, h2)
can_append(skyline, [skyline_low[i][0], h])
# skyline.append([skyline_low[i][0], h])
i += 1
j += 1
# If any partial skylines are left for skylines left or high, add them
while i < len(skyline_low):
can_append(skyline, skyline_low[i])
# skyline.append([skyline_low[i][0], skyline_low[i][1]])
i += 1
while j < len(skyline_high):
can_append(skyline, skyline_high[j])
# skyline.append([skyline_high[j][0], skyline_high[j][1]])
j += 1
return skyline
def get_skyline(buildings, low, high):
# print(low, high)
if low == high:
# Base case - Single building
skyline = []
p1 = [buildings[low][0], buildings[low][1]]
p2 = [buildings[low][2], 0]
skyline = [p1, p2]
return skyline
else:
# Recursive case - Recurse until base case then merge
mid = (low+high) // 2
skyline_low = get_skyline(buildings, 0, mid)
skyline_high = get_skyline(buildings, mid+1, high)
skyline = merge_skylines(skyline_low, skyline_high)
return skyline
def main():
buildings = get_input()
print(get_skyline(buildings, 0, len(buildings)-1))
if __name__ == '__main__':
main()
Input giving correct output
# buildings = [
# [1,11,5],
# [2,6,7],
# [3,13,9],
# [12,7,16],
# [14,3,25],
# [19,18,22],
# [23,13,29],
# [24,4,28]
# ]
Input producing infinite loop
80 20 100
40 25 60
100 24 125
700 35 826
289 11 379
20 10 2000
357 13 573
550 35 750
667 33 823
825 23 921
180 20 200
940 65 960
170 12 185
723 38 808
1289 23 1329
1120 11 1200
1357 14 1573
1520 25 1700
1627 121 1843
1825 23 1921
380 220 400
540 215 560
900 24 925
720 59 856
1289 34 1379
420 80 500
1357 16 1573
1550 25 1750
567 23 623
725 21 821
1180 21 1200
980 55 990
1170 112 1185
1723 28 1808
1489 21 1529
1320 13 1420
1877 55 1893
1720 25 1880
1000 12 1100
1345 25 1363
[1]: https://www.geeksforgeeks.org/the-skyline-problem-using-divide-and-conquer-algorithm/