#Intervals

Solutions You might see this problem as one on intervals. Here, the input is sorted and the lenght of each interval is fixed (the duration of the recording). Every interval spans from ts[i] to ts[i] + duration (excluded). The solution to this problem is the cardinality of the set containing all the seconds recorded. For example, consider this input: 1 2 3 5 2 4 10 First, the app records from 2 to 7 (excluding the latter): [Read More]

Solutions This problem looks like a classical puzzle: merging overlapping intervals. A naive approach is \(O(N^2)\) and consists in checking each route with the others. In case they overlap, remove the other route from the array and merge both into the first one. The crucial condition to check if two routes overlap is (assuming route1 precedes route2): 1 route1.end >= route2.begin For example: 1 2 3 1 5 3 6 10 32 1 5 overlaps with 3 6, indeed 5 >= 3. [Read More]

Solutions This is a problem on intervals, such as this and this. In this challenge, the main point is to find an efficient way to insert an interval into an array of already sorted and non-overlapping intervals. The naive solution is to just insert it at the end of the array, sort again and finally merge new overlapping pairs. The cost is in the order of \(O(N \cdot logN)\) (and includes also the possible hidden cost of relocating the array, in case the space is not enough). [Read More]