Research assistant interview questions shared by candidates
Recently I attended the interview at Google and I was asked "You are given a sorted list of disjoint intervals and an interval, e.g. [(1, 5), (10, 15), (20, 25)] and (12, 27). Your task is to merge them into a sorted list of disjoint intervals: [(1, 5), (10, 27)]."
You can use line-sweep algorithm for that.
First you need to sort the pairs according to their starts. Then we compare each two first pair together if they have intersection or not. if the end of the first pair is greater or equal to beginning of the second pair then they have intersection and it is obviously : start = min(start_first pair, start_second pair), end= max(end_first pair, end_second pair); this new pair will be compared with the next pair.. till the end. if there is not an intersection we leave it az an interval. We can use queue to hold the pairs