Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Solution: Intervals Intersection

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Anonymous

· 2 years ago

#class Interval:
#  def __init__(self, start, end):
#    self.start = start
#    self.end = end


class Solution:
  def merge(self, intervals_a, intervals_b):
    result = []
   
    def do_intersect(a, b):
      return (a.end <= b.end and b.start <= a.end) or (b.end <= a.end and a.start <= b.end)

    i = j = 0 

    while i < len(intervals_a) and j < len(intervals_b):
      # in there is intersection add the point
      if do_intersect(intervals_a[i], intervals_b[j]):
        result.append(Interval(max(intervals_a[i].start, intervals_b[j].start), min(intervals_a[i].end, intervals_b[j].end)))
      
      # move the smaller interval 
      if intervals_a[i].end < intervals_b[j].end:
        i += 1
      elif intervals_a[i].end == intervals_b[j].end and intervals_a[i].start <
A

Anonymous

· 3 years ago

Code part : if intervals_a[i].end < intervals_b[j].end:         i += 1       else:         j += 1

Didnt understand this part of the code.

Show 1 reply
A

Anonymous

· 3 years ago

  i,j,start,end = 0,0,0,1
  while i<len(intervals_a) and j<len(intervals_b):
    a=intervals_a[i]
    b=intervals_b[j]
    interval = [max(a[start], b[start]), min(a[end], b[end])]
    
    if interval[start]<=interval[end]:
      result.append(interval)
    
    if (a[end] > b[end]):
      j+=1
    else:
      i+=1
A

Anonymous

· 4 years ago

I've noticed in the previous problems, we calculate the minimum of the overlaps start time and maximum of end times, but in this question we are doing the reverse. Is there some keywords/hints from reading the problem on how to know which method to use? Thanks

Show 1 reply
A

Anonymous

· 5 years ago

Wont the Space Complexity of this solution be O(N+M) which is the worst case?

Show 5 replies
A

Anonymous

· 5 years ago

Second block of comment for python3 solution has a typo - the code checks if intervals_b[j]'s start time lies within intervals_a[i].

Show 1 reply

Reading Progress

0%

Vote for new content