Yioop - PHP Search Engine

-- Apr 6 In-Class Exercise

Sort list by first index Start, end = list[0][0] for(int i = 1; i < list.length(); I++) {

	if( list[start][0] == list[I][0] && list[start][1] < list[i][1] ) {
		list.remove(list[start][0], list[start][1])
		start, end = list[i]
	} else if ( start < list[i][0] && list[start][1] < list[i][1] ) {
		start = list[i][0];
	}

} Return list; Time complexity O( n* logn)

Sort list by first index Start, end = list[0][0] for(int i = 1; i < list.length(); I++) { if( list[start][0] == list[I][0] && list[start][1] < list[i][1] ) { list.remove(list[start][0], list[start][1]) start, end = list[i] } else if ( start < list[i][0] && list[start][1] < list[i][1] ) { start = list[i][0]; } } Return list; Time complexity O( n* logn)

-- Apr 6 In-Class Exercise

def GS(pairs): 
 
   pairs = sorted(pairs, reverse=True)
   min_value, max_value = float("-inf"), float("-inf")
    for index, (start, end) in enumerate(pairs):
        if start <=min_value and end >= max_value:
            pairs.pop(index)
        else:
           min_value, max_value = start, end
    return pairs

(Edited: 2022-04-11)

<pre>def GS(pairs): pairs = sorted(pairs, reverse=True) min_value, max_value = float("-inf"), float("-inf") for index, (start, end) in enumerate(pairs): if start <=min_value and end >= max_value: pairs.pop(index) else: min_value, max_value = start, end return pairs </pre>

-- Apr 6 In-Class Exercise

genGCList(list){

    sort list by start index // nlogn
    result = []
    result.append(list[0])
    for i=1 to len(list) - 1 {      // n
        prev, curr = result[last_elem], list[i]
        if curr[0] <= prev[1] and curr[1] <= prev[1]{
            result.pop()
        }
        result.append(curr)
    }
    return result

}

time complexity: O(nlogn)

genGCList(list){ sort list by start index // nlogn result = [] result.append(list[0]) for i=1 to len(list) - 1 { // n prev, curr = result[last_elem], list[i] if curr[0] <= prev[1] and curr[1] <= prev[1]{ result.pop() } result.append(curr) } return result } time complexity: O(nlogn)

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

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