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
else:
break
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]:
continue
if interval[0] > new_interval[1]:
intervals.insert(i, new_interval)
inserted_index = i
break
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
break
if inserted_index is not None:
merge_intervals_from_index(intervals, inserted_index)
else:
intervals.append(new_interval)
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)
print(interval_list)
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.