Please post your solution to the Apr 6 In-Class Exercise to this thread.

Best,

Chris

def GS(intervals):

   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

Time complexity: O(n log(n))

for i in range(0,len(S)):

   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)

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

def computeGS(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

def computeGS(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)

func GClist (sList) 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)