Teaching Kids Programming – Compute the Intersection of the Intervals

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a two-dimensional integer list intervals of the form [start, end] representing intervals (inclusive), return their intersection, that is, the interval that lies within all of the given intervals.

You can assume that the intersection will be non-empty.

Constraints
1 ≤ n ≤ 100,000 where n is the length of intervals
Example 1
Input

1 2 3 4 5

intervals = [     [1, 100],     [10, 50],     [15, 65] ]

intervals = [
    [1, 100],
    [10, 50],
    [15, 65]
]

Output
[15, 50]
Explanation
Consider the ranges [1, 100], [10, 50], [15, 65] on a line. The range [15, 50] is the only interval that is included by all of them.

Interval Intersection Algorithm

Given two intervals, the intersection can be checked easily. The intersection, if there is any, must be formed by [left, right] where left is the maximum of two starting points, and right is the minimal of two finishing points.

If the left is bigger than right, these two intervals won’t have any intersection.

The complexity of the below intersection algorithm is O(N) where we need to process each (N) intervals. The space complexity is O(1) constant.

1
2
3
4
5
6
7
8
9
10
11

lass Solution:
    def intervalIntersection(self, intervals):
        if len(intervals) == 0:
            return None
        left, right = intervals[0][0], intervals[0][1]
        for i in intervals:
            left = max(left, i[0])
            right = min(right, i[1])
        if left > right:
            return None
        return [left, right]

lass Solution:
    def intervalIntersection(self, intervals):
        if len(intervals) == 0:
            return None
        left, right = intervals[0][0], intervals[0][1]
        for i in intervals:
            left = max(left, i[0])
            right = min(right, i[1])
        if left > right:
            return None
        return [left, right]

–EOF (The Ultimate Computing & Technology Blog)