educative.io

Educative

How do we get N*log(N) complexity?

I don’t get why we have such complexity, don’t we have N^2 here?

// go through all the intervals to find each interval's next interval

  for (i = 0; i < n; i++) {

    // let's find the next interval of the interval which has the highest 'end'

    const [topEnd, endIndex] = maxEndHeap.pop();

    result[endIndex] = -1; // defaults to -1

    if (maxStartHeap.peek()[0] >= topEnd) {

      let [topStart, startIndex] = maxStartHeap.pop();

      // find the the interval that has the closest 'start'

      while (maxStartHeap.length > 0 && maxStartHeap.peek()[0] >= topEnd) {

        [topStart, startIndex] = maxStartHeap.pop();

      }

      result[endIndex] = startIndex;

      // put the interval back as it could be the next interval of other intervals

      maxStartHeap.push([topStart, startIndex]);

    }

  }

Hi @Artem!
As our solution makes use of heap. So that heap automatically sorts the intervals, our while loop will iterate (logN) times in worst case.

If you still face any confusion, feel free to ask :slightly_smiling_face: