We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Initially I tried using an interval tree, but it was too slow and timed out.
I found a completely different approach that works well and is O((n+m) log (n+m)). Treat the start and ends of intervals as events, and the values as time. Starting from the earliest time first, look at each event, and adjust the number of shots, players, and the result accordingly. There are 4 different types of events to handle:
1. X interval starts
2. X interval ends
3. player interval starts
4. player interval ends
(hint: make sure you handle ending events after starting events if you have multiple events occuring at the same time)
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Mr. X and His Shots
You are viewing a single comment's thread. Return to all comments →
Initially I tried using an interval tree, but it was too slow and timed out.
I found a completely different approach that works well and is O((n+m) log (n+m)). Treat the start and ends of intervals as events, and the values as time. Starting from the earliest time first, look at each event, and adjust the number of shots, players, and the result accordingly. There are 4 different types of events to handle: 1. X interval starts 2. X interval ends 3. player interval starts 4. player interval ends
(hint: make sure you handle ending events after starting events if you have multiple events occuring at the same time)