Home/

...

/

Problem Challenge 1

Problem Challenge 1

Dry-run templates

This is the implementation of the solution provided for the problem posed in the Problem Challenge 1 lesson:

Press + to interact
Python 3.5
from heapq import *
class Interval:
  def __init__(self, start, end):
    self.start = start
    self.end = end
def find_next_interval(intervals):
  n = len(intervals)
  # heaps for finding the maximum start and end
  maxStartHeap, maxEndHeap = [], []
  result = [0 for x in range(n)]
  for endIndex in range(n):
    heappush(maxStartHeap, (-intervals[endIndex].start, endIndex))
    heappush(maxEndHeap, (-intervals[endIndex].end, endIndex))
  # go through all the intervals to find each interval's next interval
  for _ in range(n):
    # let's find the next interval of the interval which has the highest 'end'
    topEnd, endIndex = heappop(maxEndHeap)
    result[endIndex] = -1  # defaults to - 1
    if -maxStartHeap[0][0] >= -topEnd:
      topStart, startIndex = heappop(maxStartHeap)
      # find the the interval that has the closest 'start'
      while maxStartHeap and -maxStartHeap[0][0] >= -topEnd:
        topStart, startIndex = heappop(maxStartHeap)
      result[endIndex] = startIndex
      # put the interval back as it could be the next interval of other intervals
      heappush(maxStartHeap, (topStart, startIndex))
  return result
def main():
  result = find_next_interval(
    [Interval(2, 3), Interval(3, 4), Interval(5, 6)])
  print("Next interval indices are: " + str(result))
  result = find_next_interval(
    [Interval(3, 4), Interval(1, 5), Interval(4, 6)])
  print("Next interval indices are: " + str(result))
main()

Students may be encouraged to run through the provided solution with the following sample inputs:

Sample Input #1

intervals: [(2,3),(3,4),(5,6)]

Iteration No.

Line No.

maxStartHeap

maxEndHeap

topEnd

topStart

startIndex

result

-

14

[]

[]

-

-

-

[0,0,0]

-

17-19

[(-5, 2), (-2, 0), (-3, 1)]

[(-6, 2), (-3, 0), (-4, 1)]

-

-

-

[0,0,0]

1

24

[(-5, 2), (-2, 0), (-3, 1)]

[(-4, 1), (-3, 0)]

-6

-

-

[0,0,0]

1

26-33

[(-5, 2), (-2, 0), (-3, 1)]

[(-4, 1), (-3, 0)]

-6

-

-

[0, 0, -1]

2

24

[(-5, 2), (-2, 0), (-3, 1)]

[(-3, 0)]

-4

-

-

[0, 0, -1]

2

26-33

[(-5, 2), (-2, 0), (-3, 1)]

[(-3, 0)]

-4

-5

2

[0, 2, -1]

3

24

[(-3, 1), (-2, 0)]

[]

-3

-5

-

[0, 2, -1]

3

26-33

[(-3, 1), (-2, 0)]

[]

-3

-3

1

[1, 2, -1]

Sample Input #2

intervals: [(3,4),(1,5),(4,6)]

Iteration No.

Line No.

maxStartHeap

maxEndHeap

topEnd

topStart

startIndex

result

-

14

[]

[]

-

-

-

[0,0,0]

-

17-19

[(-4, 2), (-1, 1), (-3, 0)]

[(-6, 2), (-4, 0), (-5, 1)]

-

-

-

[0,0,0]

1

24

[(-4, 2), (-1, 1), (-3, 0)]

(-5, 1), (-4, 0)]

-6

-

-

[0,0,0]

1

26-33

[(-4, 2), (-1, 1), (-3, 0)]

(-5, 1), (-4, 0)]

-6

-

-

[0, 0, -1]

2

24

[(-4, 2), (-1, 1), (-3, 0)]

[(-4, 0)]

-5

-

-

[0, 0, -1]

2

26-33

[(-4, 2), (-1, 1), (-3, 0)]

[(-4, 0)]

-5

-

-

[0, -1, -1]

3

24

[(-4, 2), (-1, 1), (-3, 0)]

[]

-4

-

-

0, -1, -1]

3

26-33

[(-4, 2), (-1, 1), (-3, 0)]

[]

-4

-4

2

[2, -1, -1]

Step-by-step solution construction

As a first step, let’s construct two heaps maxStartHeap and maxEndHeap to store the intervals in sorted order. maxStartHeap contains intervals sorted by the start time, whereas, maxEndHeap contains intervals sorted by the end time (lines 28-30). Each entry in the heaps contains the interval and the index of the interval from the intervals array.

Press + to interact
Python 3.5
from heapq import *
 
 
class Interval:
  def __init__(self, start, end):
    self.start = start
    self.end = end
  def __str__(self):
    return "(" + str(self.start) + ", " + str(self.end)+ ")"
 
def intervals_to_str(intervals):
  out = "["
  for j in range(len(intervals)):
    if(j > 0):
      out += ", "
    out += str(intervals[j])
  out += "]"
  return out
 
 
def find_next_interval(intervals):
  n = len(intervals)
 
  # heaps for finding the maximum start and end
  maxStartHeap, maxEndHeap = [], []
 
  result = [0 for x in range(n)]
  for endIndex in range(n):
    heappush(maxStartHeap, (-intervals[endIndex].start, endIndex))
    heappush(maxEndHeap, (-intervals[endIndex].end, endIndex))
  print("\tmaxStartHeap: Intervals heapified by the start time: " + str(maxStartHeap))
  print("\tmaxEndHeap: Intervals heapified by the end time: " + str(maxEndHeap))
 
  print("\tresult: " + str(result))
  return result
 
 
def main():
 
  intervals = [[Interval(2, 3), Interval(3, 4), Interval(5, 6)],
               [Interval(3, 4), Interval(1, 5), Interval(4, 6)]]
 
  for i in range(len(intervals)):
    print("Find next interval indices for: ",end = "")
    print(intervals_to_str(intervals[i]))
    result = find_next_interval(intervals[i])
    print("Next interval indices are: " + str(result))
    print(("-"*100)+"\n")
 
 
main()

The code below iterates through all intervals in the maxEndHeap.

For each interval’s end time topEnd in the maxEndHeap, we pop maxStartHeap only if its top interval’s start time is greater than or equal to topEnd (lines 35-47).

Press + to interact
Python 3.5
from heapq import *
class Interval:
  def __init__(self, start, end):
    self.start = start
    self.end = end
  def __str__(self):
    return "(" + str(self.start) + ", " + str(self.end)+ ")"
 
def intervals_to_str(intervals):
  out = "["
  for j in range(len(intervals)):
    if(j > 0):
      out += ", "
    out += str(intervals[j])
  out += "]"
  return out
def find_next_interval(intervals):
  n = len(intervals)
  # heaps for finding the maximum start and end
  maxStartHeap, maxEndHeap = [], []
  result = [0 for x in range(n)]
  for endIndex in range(n):
    heappush(maxStartHeap, (-intervals[endIndex].start, endIndex))
    heappush(maxEndHeap, (-intervals[endIndex].end, endIndex))
  print("\tmaxStartHeap: Intervals heapified by the start time: " + str(maxStartHeap))
  print("\tmaxEndHeap: Intervals heapified by the end time" + str(maxEndHeap))
  # go through all the intervals to find each interval's next interval
  for _ in range(n):
    # let's find the next interval of the interval which has the highest 'end'
    topEnd, endIndex = heappop(maxEndHeap)
    print("\ttopEnd: " + str(topEnd))
    result[endIndex] = -1  # defaults to - 1
    if -maxStartHeap[0][0] >= -topEnd:
      topStart, startIndex = heappop(maxStartHeap)
      print("\ttopStart: " + str(topStart))
      result[endIndex] = startIndex
    print("\tmaxStartHeap: " + str(maxStartHeap))
    print("\tmaxEndHeap: " + str(maxEndHeap))
    print("\tresult: " + str(result))
  return result
def main():
 
  intervals = [[Interval(2, 3), Interval(3, 4), Interval(5, 6)],
               [Interval(3, 4), Interval(1, 5), Interval(4, 6)]]
 
  for i in range(len(intervals)):
    print("Find next interval indices for: ",end = "")
    print(intervals_to_str(intervals[i]))
    result = find_next_interval(intervals[i])
    print("Next interval indices are: " + str(result))
    print(("-"*100)+"\n")
 
main()

In the code above, we compare end time of the top interval in the maxEndHeap with the start time of the top interval in the maxStartHeap. However, if we observe carefully, the top interval in the maxStartHeap might not be the best match. There may be subsequent intervals whose start time is closer to the end time of the current interval. Hence, we should keep traversing the maxStartHeap until we get an interval that starts before the end time of the top interval in the maxEndHeap.

In the code below, we add a while loop (see highlighted section) to pop maxStartHeap as long as the condition -maxStartHeap[0][0] >= -topEnd remains true.

After the loop, we update the result array with the index of the closest interval found.

Press + to interact
Python 3.5
from heapq import *
class Interval:
  def __init__(self, start, end):
    self.start = start
    self.end = end
  def __str__(self):
    return "(" + str(self.start) + ", " + str(self.end)+ ")"
 
def intervals_to_str(intervals):
  out = "["
  for j in range(len(intervals)):
    if(j > 0):
      out += ", "
    out += str(intervals[j])
  out += "]"
  return out
def find_next_interval(intervals):
  n = len(intervals)
  # heaps for finding the maximum start and end
  maxStartHeap, maxEndHeap = [], []
  result = [0 for x in range(n)]
  for endIndex in range(n):
    heappush(maxStartHeap, (-intervals[endIndex].start, endIndex))
    heappush(maxEndHeap, (-intervals[endIndex].end, endIndex))
  print("\tmaxStartHeap: Intervals heapified by the start time: " + str(maxStartHeap))
  print("\tmaxEndHeap: Intervals heapified by the end time" + str(maxEndHeap))
  # go through all the intervals to find each interval's next interval
  for _ in range(n):
    # let's find the next interval of the interval which has the highest 'end'
    topEnd, endIndex = heappop(maxEndHeap)
    print("\ttopEnd: " + str(topEnd))
    result[endIndex] = -1  # defaults to - 1
    if -maxStartHeap[0][0] >= -topEnd:
      topStart, startIndex = heappop(maxStartHeap)
      print("\ttopStart: " + str(topStart))
      # find the the interval that has the closest 'start'
      while maxStartHeap and -maxStartHeap[0][0] >= -topEnd:
        topStart, startIndex = heappop(maxStartHeap)
        print("\ttopStart: " + str(topStart))
      result[endIndex] = startIndex
      # put the interval back as it could be the next interval of other intervals
      heappush(maxStartHeap, (topStart, startIndex))
    print("\tmaxStartHeap: " + str(maxStartHeap))
    print("\tmaxEndHeap: " + str(maxEndHeap))
    print("\tresult: " + str(result))
  return result
def main():
 
  intervals = [[Interval(2, 3), Interval(3, 4), Interval(5, 6)],
               [Interval(3, 4), Interval(1, 5), Interval(4, 6)]]
 
  for i in range(len(intervals)):
    print("Find next interval indices for: ",end = "")
    print(intervals_to_str(intervals[i]))
    result = find_next_interval(intervals[i])
    print("Next interval indices are: " + str(result))
    print(("-"*100)+"\n")
 
main()