design an algorithm to check if there are overlaps between a group of intervals

Question

Dean · Accepted Answer

Well, good idea to sort the intervals, but not efficient enough because the number of intervals may be large. Sorting the same group twice may be unacceptable. Why not sort the group by their right edge and then traverse the sorted list to check if there is overlap? If there is an overlap, the left edge of the latter interval must be smaller than the former interval's right edge. So if we use merge sort, then sorting needs O(nlogn) and traverse the list needs O(n). The total complexity should be O(nlogn).

mp · Answer

Sort all left endpoints of your intervals into array a, sort all right endpoints into array b. Go along your left endpoints (array a) till you overstep the first element in the array b. If it happens => there is no common overlap for the set of all intervals. It means, that you found an interval with left endpoint being to the right of the right endpoint of another interval => these two do not overlap! Basically you have to check that all right endpoints are on the right (=less) than the minimal left endpoint.

lsp · Answer

This question was on my Microsoft interview

Google

Pergunta de entrevista da empresa Google

Respostas da entrevista

Empresas seguidas

Buscas de vagas