Yioop - PHP Search Engine

Apr 6 In-Class Exercise.

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

Best,

Chris

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

-- Apr 6 In-Class Exercise

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

(Edited: 2022-04-06)

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

-- Apr 6 In-Class Exercise

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

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

-- Apr 6 In-Class Exercise

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)

<pre> 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) </pre>

-- Apr 6 In-Class Exercise

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

<pre> 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 </pre>

-- Apr 6 In-Class Exercise

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

(Edited: 2022-04-09)

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

-- Apr 6 In-Class Exercise

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)

(Edited: 2022-04-11)

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)

-- Apr 6 In-Class Exercise

 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)

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)

-- Apr 6 In-Class Exercise

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)

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)

-- Apr 6 In-Class Exercise

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)

<pre> 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) </pre>