educative.io

Educative

More intuitive explanation?

I was wondering if there was any chance that the solution could add in a more intuitive explanation of how to go from the N^2 solution to arrive at the 2 heap solution.

It seems rather difficult to be able to go from the problem β†’ O(n^2) β†’ 2 heap solution. I mean someone had to have arrive at the solution somehow and I am hoping how I could gain the intuition of how to get there rather than memorize a solution.

Thanks!


Type your question above this line.

Course: https://www.educative.io/collection/5668639101419520/5671464854355968
Lesson: https://www.educative.io/collection/page/5668639101419520/5671464854355968/5028748841713664

Hi @adrian1,

I agree, the course should explain how one can go from a simple N^2 solution to a NLogN solution.

The solution lies in the problem itself.

When we write a N^2 solution we fail to identify the underlying patterns of the problem. (assuming these intervals are of time) The underlying pattern is… if the max end time(interval A) is greater than a max start time(interval B) then that interval B will not be the next interval for A or any other smaller start values. If it is smaller then we find the closest(top start time but smaller than the end time of interval A) start time.

To leverage these fundamental properties of max start end times we use heaps, which allow us to find the max of a set of numbers with least amount of added time complexity.

To learn and identify these patterns, one needs experience(practice) or a good memory.

I hope this was helpful!

2 Likes