Amazon | SDE 2 Onsite | Patches on an airport runway (solution needed)
Anonymous User
549

Imagine there's an airport road (consider it as a 1D line). There are various potholes that form on the runway at different times across the runway. When that happens, the potholes are patched. You're given x1 and x2, which are endpoints of the patches covering the pothole.
x1, x2 are lists of integers representing endpoints of patch, in the chronological order (as the pothole occurs).
x1: [0, 1, 30 , 70], x2: [4, 3, 60, 90]

Find the total number of patches in the end.

For this example, the first pothole is patched from (0,4). So num_patches = 1
The second pothole occurs within this pothole (1,3). So another patch is created and thus this is counted as a new patch. So, num_patches = 2
(30,60) is a new patch -> num_patches=3
Same for (70,90) -> num_patches = 4
So for this example, answer = 4

Ex:2 :
x1: [1, 0, 30 , 70], x2: [3, 4, 60, 90]
Here, (1,3) is patched first. So num_patches = 1
Now, a bigger pothole forms covering the already patched area of (1,3). So now a bigger patch is formed from (0,4). Thus, num_patches is still equal to 1.
(30,60) -> num_patches=2
(70,90) -> num_patches =3
So, answer is 3 for this example.

Note that potholes can form at any location and doesn't have to be in increasing order.
Ex: x1=[1,30,70,0], x2=[3,60,90,4]

How to solve this?

To me, this felt a bit similar to merging overlapping intervals: https://leetcode.com/problems/merge-intervals/

Comments (3)