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.
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
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.
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.
08:42: algorithm
14:16: to code
04:58: to fix the sort() method usage.
UPDATE(2023-01-29): solved again with sorted() method.
Comments
Post a Comment