Checking whether interval (a,b) is covered given 1-D list of coordinates

Question

Given 1-D list of co-ordinates determine if interval (a,b) is covered

Ex - [(2,5), (5,7),(1,4)] and interval = (1,6)
return true
Explanation - Points 1 to 6 lies in list of interval given 1 to 4. 2 to 5 and 5 to 7.

[(1,4),(6,7),(2,5)] and interval - (1,6)
return false

Explanation - Distance between 5 to 6 is not covered in the list given so return false


Answer

I encounter similar problems in different flavors in the past. As usual, I used a sorting algorithm to solve this problem but this time I asked myself, "can we do better and differently?".

In this posting, I will introduce a new way to solve this problem.

Original way - Sorting and Merging intervals: $O(N log N)$ (N is the number of intervals)

In this method, we solve the problem by following three steps.

Step 1: sort intervals by start time - $O(N log N)$

Step 2: scan the sorted list of intervals and merge overlapping intervals - $O(N)$

Step 3: scan the merged interval and check if the target interval is covered. - $O(N)$

New alternative - Using Matrix to keep track of covered range: $O(N * (max - min)^2)$

CAUTION: This way is only useful if the interval of max and min is relatively small (e.g. 24 hrs).
In that case $O(N * (max -min)^2$) will be close to $O(N)$

Given that we have more interval ranges than the length of the overall interval (max -min), we can solve this problem in $O(N)$ time by doing the following steps:

Step 1: scan the input intervals and find out the min and max values. $O(N)$

Step 2: create a new 1-D array filled with 0 with a length of (max - min + 1), Matrix

Step 3. scan the input intervals and for each integer, i in each interval, fill the Matrix[i] with 1.
         Don't forget the interval is [start, end) where the end is not included.

Step 4: scan the target interval and for each integer, t in the target interval, check if Matrix[t - min] is 1. If not return False.

Here is the complete python solution for both methods.

	def compare(left, right):
	if left[0] < right[0]:
	return -1
	else:
	return 1
	class MergeInterval:
	def is_covered(self, list, interval):
	#sort element by the start value
	sorted_list = sorted(list, cmp=compare)
	#merge the list if possible
	merged = []
	prev = None
	for i in sorted_list:
	if prev != None:
	#overlap case, extend prev
	if self.not_overlap(prev, i) != True:
	prev = [prev[0], i[1]]
	else:
	#not overlap, add prev to merged list and set preve to current interval
	merged.append(prev)
	prev = i
	else:
	prev = i
	if prev != None:
	merged.append(prev)
	#check if give interval is covered.
	for m in merged:
	if interval[0] >= m[0] and interval[1] <= m[1]:
	return True
	return False
	def not_overlap(self, prev, next):
	#prev's end is less than current's start
	return prev[1] < next[0]
	class MatrixBasedChecker:
	def is_covered(self, list, interval):
	min = max = None
	for i in list:
	if min == None and max == None:
	min = i[0]
	max = i[1]
	else:
	if i[0] < min:
	min = i[0]
	if i[1] > max:
	max = i[1]
	#create a matrix
	matrix = [0 for i in range(max - min + 1)]
	#fill the matrix O(N*(min - max)^2)
	for i in list:
	# assuming end is not included.
	for j in range(i[0], i[1]):
	matrix[j - min] = 1
	#check if interval is covered.
	for c in range(interval[0], interval[1] + 1):
	if matrix[c - min] != 1:
	return False
	return True
	input =[[2,5], [5,7],[1,4]]
	interval = [1, 6]
	m = MergeInterval()
	m2 = MatrixBasedChecker()
	print ("input = {}, target interval = {}, is_covered = {}".format(input, interval, m.is_covered(input, interval)))
	print ("Matrix based: input = {}, target interval = {}, is_covered = {}".format(input, interval, m2.is_covered(input, interval)))
	input =[[2,5], [6,7],[1,4]]
	interval = [1, 6]
	print ("input = {}, target interval = {}, is_covered = {}".format(input, interval, m.is_covered(input, interval)))
	print ("Matrix based: input = {}, target interval = {}, is_covered = {}".format(input, interval, m2.is_covered(input, interval)))

view raw check_if_interval_is_covered.py hosted with ❤ by GitHub

If you have any questions, feel free to leave a comment.

Practice statistics:

22:00: to write up the code.

5:00: to review syntax errors, typo

UPDATE(2022-06-23): Solved the problem again and made one mistake in using sort() method in python.

	# code
	def is_covered(source, target):
	return source[0]<= target[0] and source[1] > target[1]
	def is_overlapped(prev, next):
	return prev[1] >= next[0]
	def check_overlap(input, target):
	# sort input
	input.sort(key=lambda x: x[0])
	# merge the ranges
	merged = []
	cur_range = None
	for i in range(len(input)):
	if cur_range == None:
	cur_range = input[i]
	elif is_overlapped(cur_range, input[i]):
	cur_range[0] = min(cur_range[0], input[i][0])
	cur_range[1] = max(cur_range[1], input[i][1])
	else:
	#put the current range to merged list
	merged.append(cur_range)
	cur_range = input[i]
	merged.append(cur_range)
	# search the merged list for any range containing the target
	for r in merged:
	if is_covered(r, target) == True:
	return True
	return False
	# test
	input = [[2,5], [5,7], [1,4]]
	target = [1,6]
	result = check_overlap(input, target)
	print ("for {}: is {} covered? {}".format(input, target, result))
	input = [[1,4], [6,7], [2,5]]
	target = [1,6]
	result = check_overlap(input, target)
	print ("for {}: is {} covered? {}".format(input, target, result))

view raw check_if_range_is_covered.py hosted with ❤ by GitHub

08:42: algorithm

14:16: to code

04:58: to fix the sort() method usage.

UPDATE(2023-01-29): solved again with sorted() method.

	def check_interval(intervals, test_range):
	# sort the intervals
	sorted_intervals = sorted(intervals, key=lambda i: i[0])
	# mrege intervals
	merged_internvals=[]
	cur = None
	for i in range(len(sorted_intervals)):
	if cur is None:
	cur = sorted_intervals[i]
	elif sorted_intervals[i][0] <= cur[1]:
	# merge intervals
	cur[0] = min(cur[0], sorted_intervals[i][0])
	cur[1] = max(cur[1], sorted_intervals[i][1])
	else: # no overlap
	merged_internvals.append(cur)
	cur = sorted_intervals[i]
	if cur != None:
	merged_internvals.append(cur)
	# examine the intervals
	for i in range(len(merged_internvals)):
	cur = merged_internvals[i]
	if test_range[0] >= cur[0] and test_range[1] <= cur[1]:
	return True
	return False
	input=[[2,5], [6,7], [1,4]]
	test_range=[1,6]
	expected=False
	actual=check_interval(input, test_range)
	print("actual = ", actual)
	assert expected == actual

view raw check_if_range_is_covered_2023.py hosted with ❤ by GitHub