educative.io

Educative

I believe we have missed a slight optimisation in our algorithm

I have added a case where we move both pointers if the end value is the same.

def merge(intervals_a, intervals_b):
  result = []
  # This essentially just helps us to make the subsequent selection of intervals more semantic
  start, end = 0, 1
  i, j = 0, 0
  
  # Continue running the loop until both indices of each list are in range
  while i < len(intervals_a) and j < len(intervals_b):
    # Grab the smallest end of both intervals, this is just to aid readability further down 
    smallest_end = min(intervals_a[i][end], intervals_b[j][end])

    # Check if the interval from the first list overlaps the interval from the second list
    if intervals_a[i][start] >= intervals_b[j][start] and intervals_a[i][start] <= intervals_b[j][end]:
      result.append([intervals_a[i][start], smallest_end])
    # Check if the interval from the second list overlaps the interval from the first list
    elif intervals_b[j][start] >= intervals_a[i][start] and intervals_b[j][start] <= intervals_a[i][end]:
      result.append([intervals_b[j][start], smallest_end])

    # If the end of both intervals is equal to each other, since we know that intervals
    # in each list are disjoint this means both the start and end values from an interval
    # in each list are smallest than the next interval in the same list
    # using that information we can safely move both index pointers of each list up by 1
    if intervals_a[i][end] == intervals_b[j][end]:
      i += 1
      j += 1
    elif intervals_a[i][end] < intervals_b[j][end]:
      i += 1
    else:
      j += 1

  return result

Type your question above this line.

Course: https://www.educative.io/collection/5668639101419520/5671464854355968
Lesson: https://www.educative.io/collection/page/5668639101419520/5671464854355968/6518042546667520

Hi @Demos

I think this case is already covered in the provided solution. I edited the input of the solution code by keeping the same end values and the output is covering this part also.
Please let me know if there is another case that is not covered in the solution.
thanks!

Hi @Usman_Younas I am not saying that the provided solution does not work at a specific case, it does.

What I am saying is that at the case where both interval ends are equal to each other we can move both pointers at the same time slightly improving the efficiency of the algorithm.