-- Apr 7 In-Class Exercise Thread
Given list of ordered pairs, 'S'.
Pseudo code to form a G out of it is:
def G(S):
# sort by the first interval value, if ties exist then use second value
S_sorted = quick_sort(S)
to_remove = []
for j in (0, len(S_sorted)-1):
current = S_sorted[j]
next = S_sorted[j+1]
# strict sub interval
if (current[0] < next[0] and current[1] > next[1]):
to_remove.append(current)
gc = []
for pair in S:
if pair not in to_remove: gc.append(pair)
return gc
Time complexity = Sorting + for loop to find subinterval + for loop to remove super intervals
= O(n logn) + O(n) + O(n)
= O(n logn)
(
Edited: 2021-04-12)
Given list of ordered pairs, 'S'.
'''Pseudo code''' to form a G out of it is:
<nowiki>
def G(S):
# sort by the first interval value, if ties exist then use second value
S_sorted = quick_sort(S)
to_remove = []
for j in (0, len(S_sorted)-1):
current = S_sorted[j]
next = S_sorted[j+1]
# strict sub interval
if (current[0] < next[0] and current[1] > next[1]):
to_remove.append(current)
gc = []
for pair in S:
if pair not in to_remove: gc.append(pair)
return gc
</nowiki>
'''Time complexity''' = Sorting + for loop to find subinterval + for loop to remove super intervals
= O(n logn) + O(n) + O(n)
= O(n logn)