Interview Bootcamp

0% completed

​

Solution: Intervals Intersection

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!
Debasis B

Debasis B

· 2 years 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++;
                }