educative.io

Simpler to understand solution

Courses
,
#1

I believe this solution is easier to conceptualise so I decided to share.

def insert(intervals, new_interval):
  merged = []
  start, end = 0, 1

  # Set the new interval as our base Interval
  start, end = new_interval[start], new_interval[end]
  for interval in intervals:
    # Our current Interval overlaps the base Interval
    if interval[start] <= end and interval[start] >= start:
      end = max(interval[end], end)
    # Our interval is behind their Interval so we add our v to the merged
    # start and end remain the same as they come later
    elif interval[start] < start and interval[end] < start:
      merged.append(interval)
    # The base Interval overlaps our current Interval
    # So we need to merged the Intervals
    elif interval[start] < start and interval[end] >= start:
      start = interval[start]
      end = max(interval[end], end)
    # Our Interval is ahead of the base Interval so
    # we add a new interval with the base Interval values
    # and make our current Interval the base Interval values
    elif interval[start] > end:
      merged.append([start, end])
      start, end = interval[start], interval[end]
  
  # Add the last Interval
  merged.append([start, end])
    
  return merged

Type your question above this line.

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

#2

Hi,
Your solution is incorrect as it returns an error on the first call, i.e. IndexError: list index out of range.
The new_interval contains the values 4 and 6. The length of interval is 2, but the value stored in start is 4. This results in an index error; hence, this solution is incorrect.

Regards

#3

Hi @Syed_Ayan_Haider_Naq you are right, I used the same variable names for 2 different purposes,

I have now update the solution below and it should now work.

def insert(intervals, new_interval):
  merged = []
  start, end = 0, 1

  # Set the new interval as our base Interval
  start_interval, end_interval = new_interval[start], new_interval[end]
  for interval in intervals:
    # Our current Interval overlaps the base Interval
    if interval[start] < end_interval and interval[start] >= start_interval:
      end_interval = max(interval[end], end_interval)
    # Our interval is behind their Interval so we add ours to the merged
    # start and end remain the same as they come later
    elif interval[end] <= start_interval:
      merged.append(interval)
    # The base Interval overlaps our current Interval
    # So we need to merged the Intervals
    elif interval[start] < start_interval and interval[end] > start_interval:
      start_interval = interval[start]
      end_interval = max(interval[end], end_interval)
    # Our Interval is ahead of the base Interval so
    # we add a new interval with the base Interval values
    # and make our current Interval the base Interval values
    elif interval[start] > end_interval:
      merged.append([start_interval, end_interval])
      start_interval, end_interval = interval[start], interval[end]
  
  # Add the last Interval
  merged.append([start_interval, end_interval])
    
  return merged

def main():
  print("Intervals after inserting the new interval: " + str(insert([[1, 3], [5, 7], [8, 12]], [4, 6])))
  print("Intervals after inserting the new interval: " + str(insert([[1, 3], [5, 7], [8, 12]], [4, 10])))
  print("Intervals after inserting the new interval: " + str(insert([[2, 3], [5, 7]], [1, 4])))


main()
#4

Hello @Demos
Yes this works now. Great job!

Regards