Post your solutions to the Oct 16 In-class Exercise to this thread.

Best,

Chris

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)

=> O(n^2)

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)

Pseudo-code: 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 }

Example: 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)]

Run-time: 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)

def resetarray(arr): fill array with 0s arr <- 0 return arr

def 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

gc = [[1,10],[5,9],[8,12],[15,20],[12,15]] G(gc)

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);

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

Runtime: 0(n^2)

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)

Store intervals in a class Interval that has start and end paramters u, v.

list gc = [Intervals].

Sort gc list based on the first value u.

start = gc[0].u

end = gc[0].v

create empty result list.

for interval in gc: 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.v
add last interval(start, end) to result list.

return result list.

Runtime O(n)