|
Be the first user to complete this post
|
Add to List |
438. Check if interval is covered in given coordinates
Objective: Given 1-D list of coordinates, (x1, x2), (x3, x4), , , ,(xn-1, xn)and interval (a, b). Write an algorithm to determine if interval (a,b) is covered in the list of coordinates.
Example:
Coordinates - [(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. Coordinates - [(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
Approach:
Brute Force:
Iterate through all the coordinates and for each coordinate compare the a and end with all other intervals and merge them if overlapping.
Time Complexity: O(N^2)
Better Solution - Sorting.
- Sort the given coordinates in ascending order of their start x1.
- Push first coordinate to stack.
- Iterate through the rest of the coordinates, for each current coordinate -
- Pop the top coordinate form the stack. Let's call it previous.
- Check if x2 of previous is greater than x1 for current (means current coordinate is started before the previous coordinate was ended, so these two coordinates can be merged). If yes then update the x2 of previous to x2 of current coordinate, else just push the current coordinate to stack (no need to check the previous coordinate with other coordinates because coordinates are sorted in ascending order).
- Now all the possible coordinates are merged.
- Pop coordinates from stack one at a time and checks if given interval lies within the range of popped coordinates, return true.
- If the last step is executed and no coordinates were found where given interval lies in the range, return false.
Time Complexity: O(nlogn)
Output:
Given Coordinates: [[2,5], [5,7], [1,4]] Given Interval: [1,6] Given interval is COVERED in coordinates ------------------------------------------------------- Given Coordinates: [[1,7], [2,5], [5,7]] Given Interval: [1,8] Given interval is NOT COVERED in coordinates