Programming Solutions to Count Fully Contained Intervals in Python

💡 Problem Formulation: Given a collection of intervals, each specified as a pair of numbers, the challenge is to count how many intervals are completely contained within others. For example, in a list [(1, 5), (2, 3), (4, 6)], the interval (2, 3) is entirely contained within (1, 5). The desired output here would be 1.

Method 1: Brute Force Comparison

This method involves iterating over all pairs of intervals and checking whether one interval is entirely within another interval. It’s simple and effective for short lists but falls prey to inefficiency with large datasets due to its O(n²) time complexity.

Here’s an example:

def count_contained(intervals):
    contained_count = 0
    for i, (start_i, end_i) in enumerate(intervals):
        for j, (start_j, end_j) in enumerate(intervals):
            if i != j and start_j > start_i and end_j < end_i:
                contained_count += 1
                break
    return contained_count

intervals = [(1, 5), (2, 3), (4, 6)]
print(count_contained(intervals))

Output: 1

The function count_contained() takes a list of intervals and uses two nested loops to compare each interval against all others, incrementing contained_count whenever it finds an interval that fits wholly inside another. The use of enumerate() ensures that an interval is not compared with itself.

Method 2: Sorting and Linear Scan

By first sorting intervals based on their start points (and secondarily on end points), one can iterate through the list once to find contained intervals with better performance, typically O(n log n) due to sorting.

Here’s an example:

def count_contained_sorted(intervals):
    contained_count = 0
    intervals.sort(key=lambda x: (x[0], -x[1]))
    max_end = -float('inf')

    for (start, end) in intervals:
        if end <= max_end:
            contained_count += 1
        else:
            max_end = end

    return contained_count

intervals = [(1, 5), (2, 3), (4, 6)]
print(count_contained_sorted(intervals))

Output: 1

The sorted list allows count_contained_sorted() to track the maximum end point it encounters. Any subsequent interval whose end point is less than or equal to this maximum is guaranteed to be contained. Thus, we can count all such intervals with just one pass post-sorting.

Method 3: Interval Trees

For larger datasets, interval trees provide a data structure optimized for interval comparisons. They allow us to query which intervals contain a given point (or another interval) efficiently, generally in O(log n).

Here’s an example:

from intervaltree import IntervalTree

def count_contained_interval_tree(intervals):
    tree = IntervalTree()
    for start, end in intervals:
        tree[start:end] = True

    contained_count = 0
    for start, end in intervals:
        containing_intervals = tree.envelop(start, end)
        if len(containing_intervals) > 1:
            contained_count += 1

    return contained_count

intervals = [(1, 5), (2, 3), (4, 6)]
print(count_contained_interval_tree(intervals))

Output: 1

IntervalTree from the intervaltree Python package is used to construct an efficient structure for interval containment checks. The method envelop() finds intervals that contain a given range, facilitating the tally of contained intervals.

Method 4: Custom Data Structure

Creating a custom data structure that stores intervals in an optimized fashion can improve search efficiency for interval containment, especially for domain-specific knowledge about the intervals that can be leveraged.

Here’s an example:

# This example is theoretical and does not represent actual Python code
def count_contained_custom_structure(intervals):
    pass
    # Implementation of a custom data structure would go here

intervals = [(1, 5), (2, 3), (4, 6)]
# The actual function call and use would depend on how the custom data structure is implemented

This method requires an in-depth understanding of the specific use case and problems at hand, as the performance improvements are entirely dependent on the tailored nature of the solution.

Bonus One-Liner Method 5: List Comprehension with Any

Pythonic and concise, this method uses a list comprehension combined with the any() function to quickly ascertain if an interval is contained within any other interval in a single, compact line of code.

Here’s an example:

intervals = [(1, 5), (2, 3), (4, 6)]
contained_count = sum(any(start > s and end < e for s, e in intervals) for start, end in intervals)
print(contained_count)

Output: 1

Using list comprehension, the one-liner effectively mimics a nested loop with any() testing for containment in a succinct functional style.

Summary/Discussion

• Method 1: Brute Force Comparison. Straightforward and easy to implement. Inefficient for large data sets due to O(n²) time complexity.
• Method 2: Sorting and Linear Scan. Improves efficiency through sorting and a subsequent linear pass. Performs well on most datasets with a time complexity of O(n log n).
• Method 3: Interval Trees. Offers a significant performance boost for large or dynamic sets of intervals. Implementations may require additional space and understanding of the data structure.
• Method 4: Custom Data Structure. Potentially the most efficient but requires significant domain knowledge to implement correctly. Not a general solution but powerful when applicable.
• Method 5: List Comprehension with Any. A compact and Pythonic way, best suited for small to medium-sized datasets, and requiring no additional data structure.