Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Intervals Intersection (medium)

Problem Statement

Given two lists of intervals, find the intersection of these two lists. Each list consists of disjoint intervals sorted on their start time.

Example 1:

Input: arr1=[[1, 3], [5, 6], [7, 9]], arr2=[[2, 3], [5, 7]]
Output: [2, 3], [5, 6], [7, 7]
Explanation: The output list contains the common intervals between the two lists.

Example 2:

Input: arr1=[[1, 3], [5, 7], [9, 12]], arr2=[[5, 10]]
Output: [5, 7], [9, 10]
Explanation: The output list contains the common intervals between the two lists.

Constraints:

  • `0 <= arr1.length, arr2

.....

.....

.....

Like the course? Get enrolled and start learning!
B

Baraa Attabbaa

· 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

Avinash Agarwal

· 4 years ago

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

Show 5 replies
H

hj3yoo

· 4 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
A

Alan Lo

· 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 2 replies
Anupriya Ramachandran

Anupriya Ramachandran

· 2 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
Mohammed Dh Abbas

Mohammed Dh Abbas

· 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 <
Roman Kishchenko

Roman Kishchenko

· 2 years ago

class Solution {

  public List<Interval> merge(Interval[] left, Interval[] right) {
    List<Interval> result = new ArrayList<Interval>();

    int l = 0;
    int r = 0;
    while (l < left.length && r < right.length) {
      // Skipping an interval from the left if it ends before an 
      // interval from the right starts
      if (left[l].end < right[r].start) {
        l++;
      // Similarly, skipping an interval from the right if it ends before 
      // an interval from the left starts
      } else if (right[r].end < left[l].start) {
        r++;
      } else {
        // If the first two conditions are not satisfied, there is an intersection.
        Interval intersection = new Interval(
          Math.max(left[l].start, right[r].start), 
          Math.min(left[l].e
Debasis B

Debasis B

· a year ago

public class IntervalsIntersection
{
    /// <summary>
    /// O(m + n)
    /// </summary>
    /// <param name="arr1"></param>
    /// <param name="arr2"></param>
    /// <returns></returns>
    public List<Interval> merge(Interval[] arr1, Interval[] arr2)
    {
        List<Interval> result = new List<Interval>();
        int i1 = 0, i2 = 0;
        while (i1 < arr1.Length && i2 < arr2.Length)
        {
            if (DoesIntersect(arr1[i1], arr2[i2]))
            {
                result.Add(FindIntersection(arr1[i1], arr2[i2]));
                if (IsSubInterval(arr1[i1], arr2[i2]))
                {
                    i2++;
                }
                else if (IsSubInterval(arr2[i2], arr1[i1]))
                {
                    i1++;
                }
Vladimir Surcov

Vladimir Surcov

· a year ago

if (arr1[i].start <= arr2[j].end && arr2[j].start <= arr1[i].end) {...}
Show 1 reply
Aydar Nabiev

Aydar Nabiev

· 6 months ago

The reason for it - it is easier to determine if intervals don't touch each other. In that case it is also easy to understand which one needs to 'catch up' to the other.

This task is 'inspired by' Leetcode 986 - I write this so you can go there and see example 1, the visual representation will help you reach this solution yourself, like I (thanks to this course, too) did. In my opinion, those 'ifs' which exclude all non-overlapping scenarios, seems to be better for the eye than the visually complex 'if' for overlapping.

public List<Interval> merge(Interval[] arr1, Interval[] arr2) {
    if (arr1.length == 0 || arr2.length == 0) {
        new ArrayList<>();
    }

    // we probably must create new intervals on the fly, but understanding their bounds is the hardest challenge