SHARE
TWEET

Untitled

a guest Nov 19th, 2019 99 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. input = [(1, 5, 10, 'a'), (2, 6, 20, 'b'), (3, 10, 70, 'c'), (5, 12, 30, 'd'), (7, 15,50, 'e'),
  2.              (13, 17, 10, 'f'), (15, 20, 30, 'g'), (14, 25, 40, 'h'), (18, 26, 20, 'i')]
  3.  
  4. input = sorted(input, key=lambda tup: tup[1])
  5.  
  6. def find_interval(input, ith):
  7.     if(ith == 0):
  8.         return input[0][2]
  9.     else:
  10.         overlap = findOverlap(input, ith)
  11.         print(overlap, ith)
  12.         answer = []
  13.         for k in overlap:
  14.             answer.append(find_interval(input, k))
  15.         return input[ith-1][2] + min(answer)#min(find_interval(input, j) for j in overlap)
  16.            
  17.  
  18.  
  19. def findOverlap(input, ith):
  20.     overlap = []
  21.     counter = ith-1
  22.     for k in reversed(range(ith-1)):
  23.         if(input[k][1]  >= input[ith-1][0]):
  24.             overlap.append(counter)
  25.             counter = counter - 1
  26.     #print(ith, overlap)
  27.     return overlap
  28.  
  29.  
  30. print(find_interval(input, 9))
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. OK, I Understand
 
Top