Sets of intervals are often represented as a sorted list of integer pairs.

Thorough this page intervals are considered to include both ends.

The Python 3 code examples consider intervals to be lists of two integers.


A common requirement is to be able to insert a new interval into an interval set. When the new interval does not intersect with any of the existing intervals this is easy. However, if the number of intersections is not zero, making mistakes in the insertion logic is common. Therefore, I think it is worthwhile to present here well-tested code for inserting a new interval into an interval list.

The implementation presented here requires O(n) to find the insertion point, O(n) to insert, O(n) to find and merge overlapping intervals, and then O(n) to free the no longer required objects.

It is worth mentioning that even though both search steps can be improved to O(lg n), inserting into an array-based list and freeing the no longer required intervals should always be at least O(n), so you should not be able to do better than O(n) asymptotically.

However, if your interval list grows very large, I’d advise using binary search or some other technique to improve this operation as much as possible.

def test_if_interval_list_is_valid(intervals):
    for i, interval in enumerate(intervals):
        if interval[0] > interval[1]:
            return False
        if i > 0:
            if not interval[0] > intervals[i - 1][1]:
                return False
        if i + 1 < len(intervals):
            if not intervals[i + 1][0] > interval[1]:
                return False
    return True

def merge_intervals_from_index(intervals, index):
    cut_position = index + 1
    for i in range(index + 1, len(intervals)):
        if intervals[i][0] <= intervals[index][1]:
            intervals[index][1] = max(intervals[index][1], intervals[i][1])
            cut_position = i + 1
    del intervals[index + 1: cut_position]

def insert_interval(intervals, new_interval):
    inserted_index = None
    for i, interval in enumerate(intervals):
        if interval[1] < new_interval[0]:
        if interval[0] > new_interval[1]:
            intervals.insert(i, new_interval)
            inserted_index = i
        if interval[0] <= new_interval[1]:
            intervals[i][0] = min(intervals[i][0], new_interval[0])
            intervals[i][1] = max(intervals[i][1], new_interval[1])
            inserted_index = i
    if inserted_index is not None:
        merge_intervals_from_index(intervals, inserted_index)

if __name__ == '__main__':
    interval_list = []
    insertions = [[3, 4], [1, 2], [2, 3], [5, 5], [6, 6], [0, 7]]
    for insertion in insertions:
        insert_interval(interval_list, insertion)
        assert test_if_interval_list_is_valid(interval_list)

# Produces
#  [[3, 4]]
#  [[1, 2], [3, 4]]
#  [[1, 4]]
#  [[1, 4], [5, 5]]
#  [[1, 4], [5, 5], [6, 6]]
#  [[0, 7]]

An adapted version of the above algorithm is able to successfully solve this problem on LeetCode.