Here’s the problem: I have 1 timeline, but 2 types of events appear on this timeline. I want to use events of type 1 as borders in my timeline, these borders will separate events of type 2 into groups.

For example: I want to know which bird sings first every morning after sunrise. I have a list of sunrises for the last month and a list of singing events. How do I get the result without doing a 2-level nested loop?

A 2-level loop will always work (but it will be the slowest)

I want to end up with a list of pairs of the sunrise time and the first song time.

A loop like this will always work:

for sunrise in sunrises:
  for bird_song in bird_songs:
    # if the song happened before the sunrise, check the next song
    if bird_song.start_at < sunrise.at:
      continue

    # if the song happened on the next day, then let's move to the next sunrise
    if bird_song.start_at > sunrise.day_ends_at:
      break

    sunrise.first_bird_song = bird_song
    # once we found our first song, we can move on to the next sunrise
    break

But it is looping over the bird_songs too many times. For each sunrise, we start looping over bird_songs from the 1st song on. Time-wise a classical 2-level loop is considered to take about $O(N^2)$ time.

True, in our case, we loop over 2 different lists, we have S number of sunrises and B number of bird songs, so we get O(S * B). Then we also break out from the loop when we find the correct song, so we don’t really do the full B number of loops for every sunrise. But these estimations are always made with the worst-case scenario in mind, which is in our case: we have 10 million bird songs and all of them happen on the first day and before the sunrise, which brings us right into O(S * B).

One loop, two counters moving it forward

To make the above loop faster, we would need to loop over sunrises and bird_songs in alternation. We need to stop the bird_songs loop when we find the desired song, move sunrises 1 iteration further and then continue looping over bird_songs at the exact location, where we stopped looping before.

sunrise_counter = 0
song_counter = 0

while sunrise_counter < len(sunrises) and song_counter < len(bird_songs):
  bird_song = bird_songs[song_counter]
  sunrise = sunrises[sunrise_counter]

  # if the song happened before the sunrise, check the next song
  if bird_song.start_at < sunrise.at:
    song_counter += 1
    continue

  # if the song happened on the next day, then let's move to the next sunrise
  if bird_song.start_at > sunrise.day_ends_at:
    sunrise_counter += 1
    continue

  sunrise.first_bird_song = bird_song
  # once we found our first song, we can move on to the next sunrise and next song
  song_counter += 1
  sunrise_counter += 1

This while-loop is extremely similar to the 2-level loop from above. It has the same if-statements and the same comments, but its time complexity is $O(S + B)$ instead of $(S * B)$. With 30 sunrises and 10M bird songs, we land at ~10M operations instead of 300M operations.

The biggest drawback of this approach: it’s much more difficult to read and maintain. This too is an important aspect of the code.

Choose the one, which brings you more benefits.