#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]

Solutions This is a problem on intervals. A brute force solution would involve checking every pair of talks to see if they overlap. We can iterate through each talk and compare it with every other talk. If any two talks overlap, the schedule is invalid. Two talks overlap if one starts before the other ends and vice versa. This results in a nested loop where each talk is compared against all others, leading to a quadratic time complexity. [Read More]