Interval Intersection Algorithm

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
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.

Compute the Intersection of Intervals

The intersection must be the the maximum of all starting points + the minimal of all ending points. If the final start is larger than the finish, there is no intersection. We can do this in on pass. The time complexity is O(N) and the space complexity is O(1) constant.

1
2
3
4
5
6
7
8
9
10

vector<int> intervalIntersection(vector<vector<int>>& intervals) {
    int a = intervals[0][0];
    int b = intervals[0][1];
    for (auto &n: intervals) {
        a = max(a, n[0]);
        b = min(b, n[1]);
    }
    if (a > b) return {};
    return {a, b};
}

vector<int> intervalIntersection(vector<vector<int>>& intervals) {
    int a = intervals[0][0];
    int b = intervals[0][1];
    for (auto &n: intervals) {
        a = max(a, n[0]);
        b = min(b, n[1]);
    }
    if (a > b) return {};
    return {a, b};
}

–EOF (The Ultimate Computing & Technology Blog) —