You have a sorted list of intervals (sorted by start time). There are two constraints:
a. There are millions of intervals in this list.
b. The total range covered by these intervals is also very large - more than 10^6

Question:

1. How to find if '2' intervals are intersecting or conflicting. What is the time complexity of this algorithm
2. How to find if 'k' intervals are intersecting or conflicting. 'k' intervals are conflicting if they have any element in the range that is common.

Example : [10-30], [15-35], [20-40], [25-30] and k = 3
there is a conflict because at t=25 we have 4 intervals.

Approach suggested: find the min and max of the interval range and declare an array of this size. For each interval, mark the range (i.e increase it by 1). When incrementing the range if any value becomes more than 'k', it is a conflict.

Time complexity : O(n * |L|) - where |L| is the max interval size.

Interviewer was not satisfied with this response and wanted a better/efficient approach.

Any suggestions?