# 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
is greater than*x2 of previous*(means*x1 for current*is started before the*current coordinate*was ended, so these two coordinates can be merged). If yes then update the*previous coordinate*to*x2 of previous*, else just push the*x2 of current coordinate*to stack (no need to check the*current coordinate*with other coordinates because coordinates are sorted in ascending order).*previous coordinate*

- Pop the top coordinate form the stack. Let’s call it
- 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)**

**Complete Code:**

**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