output = [intervals[0]] intervals.sort(key = lambda x : (x[0], -x[1])) for idx in range(1, len(intervals)): prev, cur = output[-1], intervals[idx] if cur[0] <= prev[1] and cur[1] <= prev[1]: output.pop() output.append(cur)
return output
for j in range(i,len(S)): if S[i][0] >= S[j][0] and S[i][1] <= S[j][i] remove S[i] Time Complexity: N^2
genGCList(list){ sort list by end index //nlogn start, end = list[0] for I = 1 to list.len-1{ //n if end<list[I][1]{ res.add(start, end) start, end = list[I] } else if start<list[I][0] start = list[I][0] } return res } time complexity: O(nlogn)(Edited: 2022-04-07)
input: A list containing interval sets output: A GC list G_S_calc(List_intervals) sort(List_intervals by start index) i = 0, j = 1; len = List_intervals.len; while(i<len && j<len) { if (List_intervals[i][0] == List_intervals[j][0] && List_intervals[i][1] > List_intervals[j][1]) Eliminate List_intervals[i] i=j j=j+1 elseif (List_intervals[i][0] == List_intervals[j][0] && List_intervals[i][1] < List_intervals[j][1]) Eliminate List_intervals[j] j=j+1; elseif (List_intervals[i][1] < List_intervals[j][1]) No Elimination // both are non related intervals i=j+1, j=j+2 elseif (List_intervals[i][1] > List_intervals[j][1]) Eliminate List_intervals[i] i=j j=j+1; } return List_intervals
intervals = sorted(intervals, reverse=True) min_val, max_val = float("-inf"), float("-inf") for idx, (start, end) in enumerate(intervals): if start <= min_val and end >= max_val: intervals.pop(idx) else: min_val, max_val = start, end
return intervals
intervals.sort(key = lambda i : i[0]) output = [intervals[0]] for start, end in intervals[1:]: lastEnd = output[-1][1] if start <= lastEnd: output[-1][1] = max(lastEnd, end) else: output.append([start,end]) return output
Time complexity: O(nlogn)
GC(list of intervals){
Sort the list Pointer1 = 0; Pointer2 = 1;
length = length of list; while(Pointer1 < length and Pointer2 < length) { if (list[pointer1][0] == list[pointer2][0] and list[pointer1][1] > list[pointer2][1] Delete list[pointer1] pointer1 = poiner2; pointer2 ++; elseif (list[pointer1][0] == list[pointer2][0] and list[pointer1][1] < list[pointer2][1] Delete list[pointer2] pointer2 ++; elseif (list[pointer1][1] > list[pointer2][1]) Delete list[pointer1] pointer1 = poiner2; pointer2 ++; elseif (list[pointer1][1] < list[pointer2][1]) pointer1 = poiner2 + 1; pointer2 = pointer2 + 2; } Return(list)
sort sList by first interval ( or interval 0 ) //nLogn while not at end of list if firstInterval <= firstInterval of next pair remove interval pair
return sList
time complexity O(nlog(n)^2)
GCList(list){ sort list by end index start, end = list[0] for i = 1 to list.len-1{ //n if end<list[i][1]{ output.add(start, end) start, end = list[i] } else if start<list[i][0] start = list[i][0] } return output } Time complexity: O(nlogn)(Edited: 2022-04-11)