Algorithms to Check if Intervals are Self-Contained

You are given a two-dimensional list of integers intervals where each element is an inclusive interval [start, end]. Return whether there’s an interval which contains another interval.

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

1 2 3 4 5 6

intervals = [     [1, 3],     [4, 10],     [4, 8],     [9, 9] ]

intervals = [
    [1, 3],
    [4, 10],
    [4, 8],
    [9, 9]
]

Output
true
Explanation
[4, 10] contains [4, 8].

Example 2
Input

1 2 3 4 5

intervals = [     [1, 3],     [4, 10],     [7, 12] ]

intervals = [
    [1, 3],
    [4, 10],
    [7, 12]
]

Output
false
Explanation
No interval completely contains another.

Example 3
Input

1 2 3 4

intervals = [     [1, 5],     [1, 5] ]

intervals = [
    [1, 5],
    [1, 5]
]

Output
true

Bruteforce Algorithm to Check Intervals Self-Contained

We can perform a bruteforce search to check every two intervals which require time complexity O(N^2) quadratic. However, this is inefficient.

1
2
3
4
5
6
7
8
9
10
11
12
13

bool containedIntervals(vector<vector<int>>& intervals) {
    for (int i = 0; i < intervals.size(); ++ i) {
        for (int j = 0; j < i; ++ j) {
            auto a = intervals[i];
            auto b = intervals[j];
            if ((a[0] >= b[0] && a[1] <= b[1]) || 
                (b[0] >= a[0] && b[1] <= a[1])) {
                    return true;
                }
        }
    }
    return false;
}

bool containedIntervals(vector<vector<int>>& intervals) {
    for (int i = 0; i < intervals.size(); ++ i) {
        for (int j = 0; j < i; ++ j) {
            auto a = intervals[i];
            auto b = intervals[j];
            if ((a[0] >= b[0] && a[1] <= b[1]) || 
                (b[0] >= a[0] && b[1] <= a[1])) {
                    return true;
                }
        }
    }
    return false;
}

Sort and Check Intervals Self-Contained

We sort the intervals by starting position, and then if the starting positions are equal, we put the smaller finishing positions first. Then we can keep tracking of the current minimal and maximum interval positions, and check if the current interval is within this range.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

bool containedIntervals(vector<vector<int>>& intervals) {
    sort(begin(intervals), end(intervals), [](auto &a, auto &b) {
        return (a[0] < b[0]) || ((a[0] == b[0]) && (a[1] > b[1]));
    });
    int curMax = -INT_MAX + 1;
    int curMin = INT_MAX;
    for (auto &n: intervals) {
        if (n[0] >= curMin && n[1] <= curMax) {
            return true;
        }
        curMax = max(curMax, n[1]);
        curMin = min(curMin, n[0]);
    }
    return false;
}

bool containedIntervals(vector<vector<int>>& intervals) {
    sort(begin(intervals), end(intervals), [](auto &a, auto &b) {
        return (a[0] < b[0]) || ((a[0] == b[0]) && (a[1] > b[1]));
    });
    int curMax = -INT_MAX + 1;
    int curMin = INT_MAX;
    for (auto &n: intervals) {
        if (n[0] >= curMin && n[1] <= curMax) {
            return true;
        }
        curMax = max(curMax, n[1]);
        curMin = min(curMin, n[0]);
    }
    return false;
}

Sorting takes O(NLogN), which is apparently superior than the first bruteforce search algorithm.

–EOF (The Ultimate Computing & Technology Blog) —