inp = [[5, 9], [8, 12], [15, 20], [1, 10], [9, 11]] inp.sort(key=lambda x: x[0]) i = 0 for ele in inp: for ep in inp[i + 1:]: if (ep[0] > ele[1]): break if (ep[1] <= ele[1] and ep[0] > ele[0]): inp.remove(ele) break print(inp)
class Node: def __init__(self,key): self.left = None self.right = None self.val = key # Check if pair2 is superset of pair1 def is_super_set(pair1, pair2): if pair2[0] > pair1[0] and pair2[1] < pair1[1]: return True return False # Check if pair2 is on left side of pair1 (even if overlaps) def is_on_left(pair1, pair2): if pair2[0] < pair1[0]: return True return False # Check if pair2 is on right side of pair1 (even if overlaps) def is_on_right(pair1, pair2): if pair2[1] > pair1[1]: return True return False # Insert node to tree if it follows G(S) def insert_pair_to_tree(root, node): if is_super_set(root.val, node.val): return if is_on_right(root.val,node.val): if root.right is None: root.right = node result.append(node.val) else: insert_pair_to_tree(root.right, node) elif is_on_left(root.val, node.val): if root.left is None: root.left = node result.append(node.val) else: insert_pair_to_tree(root.left, node) l = [[5, 9], [8, 12], [15, 20], [1, 10], [10, 11], [4, 6], [10, 20]] l.sort(key = lambda x: abs(x[1] - x[0]), reverse = True) # O(nlogn) # Sort by width of pair so wide pairs are processed first result = [] #Widest pair will not be superset of any other pair result.append(l[0]) root = Node(l[0]) for i in range(1, len(l)): #(O(n)) curr_node = Node(l[i]) insert_pair_to_tree(root, curr_node) # O(log(n)) # Final time complexity of above loop O(nlogn) print(result)(Edited: 2019-10-16)
getGS((S[1], S[2], ..., S[n])) { # each S[i] is a tuple representing an interval S' = sort (S[1], S[2], ..., S[n]) by value of (S[i][2]-S[i][1]) for i := 1 to n do { if (S[i][1] < S'[i][1]) { S[i]= () # make S[i] an empty tuple } } filter(lambda a: a != (), S); // remove all empty tuples in S sort (S) by S[1]; return S }
S= [(1,10),(2, 8),(3, 5), (4,11), (6,17)] violation: (2, 8) and (3, 5) are subsets of (1, 10) (3, 5) is a subset of (2,8) S[1]-S[2]= [9, 6, 2, 7, 11], so S'= [(6,17),(1,10),(4,11), (2, 8), (3,5 )] i=1: 1<6, so S[1]= (); i=2: 2>1, so keep S[2]; i=3: 3<4, so S[3]= (); i=4: 4>2, so keep S[4]; i=5: 6>3, so keep S[5]; Now S= [(), (2, 8), (), (4,11), (6,17)] filter out (), gives result S= [(2,8),(4,11),(6,17)]
sorting step: O(nlog(n)), looping: O(n) total: O(nlog(n))
find_GC_list(list) { // list contains n pairs sort the list in increasing order of the first parameter of pairs O(nlogn) for i = 1 to n do for j = i+1 to n do if list[i][1] <= list[i+1][1] then remove(list[i]) }
Runtime : O(n*n-1) = O(n^2)(Edited: 2019-10-18)
fill array with 0s arr <- 0 return arrdef G(gc):
gc = sorted(gc,key=lambda x :x[0]) arr = resetarray(arr) for (x,y) in gc: if arr[x] == 1 and arr[y] == 1: //get the start and end index of array and the remove pair //reset array //otherwise //overlap //fill the arr indes for i in range(x,y+1): arr[i] = 1
public void FindGClist(String[] inputlist) { // Sort inputlist by the first element of the interval String[] GClist = new GClist(); String [] temparray1 = new temparray(); String [] temparray2 = new temparray(); int GClistindex = 0; for (int i =0; i <inputlist.length; i++) { int counter = 0; int LC1 = Get the first element from inputlist[i]; int UC1 = Get the second element from inputlist[i]; for (int j =0; j<inputlist.length; j++) { if(i!=j) { int LC2 = Get the first element from inputlist[j]; int UC2 = Get the second element from inputlist[j]; if(LC2>=LC1 && UC2<=UC1) { counter++ break; } } } if(counter == 0) { GClist[GClistindex] = inputlist[i]; GClistindex++; } } for (int k=0; k <GClist.length; k++) { System.out.println(GClist[k]); } }String [] inputlist = {"[1 10]","[8 12]","[15 20]","[2 10]","[3 5]","[12 15]","[1,8]"}; FindGClist(inputlist);(Edited: 2019-10-21)
compute_GS(S[1], S[2], S[3], … S[n]) Sort the list S[1], S[2], S[3], … S[n] by the first value and save in sorted_list for i in size(sorted_list) do: for j in size(sorted_list + 1) do: if i[0] < j[0] and i[1] >= j[1] then: remove sorted_list[i] return sorted_list
Input: S[1],S[2],S[3],....S[n] Get_gs(input) Sort the input list i = 0 for x in input[i]: for y in input[i+1]: if (y[0]>x[1]): break if( y[1] <= x[1] and y[0] > x[0]): remove x from input list return input list Runtime: O(n^2)
if interval.u > end || (interval.u != start && interval.v > end): add new Interval(start, end) to result list start = interval.u end = interval.v else if interval.u <= end: if interval.u == start && interval.v > end: end = interval.vadd last interval(start, end) to result list.
Runtime O(n)