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.
  1. Prepare
  2. Data Structures
  3. Advanced
  4. Mr. X and His Shots
  5. Discussions

Mr. X and His Shots

  • wallaceong_care1
     + 1 comment

    Just wanted to add explanation as to why this works.

    We are trying to get the number of overlaps by getting all the numbers of pairs - number of non overlapping pair.

    For the pair to be non-overlapping - it has to satisfy this condition. player_end < shot_start or shot_end < player_start

    Hence this means, given the player_start, we want to check the number of shot_end that are strictly smaller <.

    Hence this means, given the player_end, we want to check the number of start that are strictly larger >. 

    def solve(shots, players):
    
    start = []
    end = []
    for i in range(len(shots)):
        start.append(shots[i][0])
        end.append(shots[i][1])
    start.sort()
    end.sort()
    ans = len(shots) * len(players)
    for player_start, player_end in players:
        
        shots_larger_than_player_end = len(start) - bisect(start, player_end)
        shorts_smaller_than_player_start = bisect_left(end, player_start)
        ans -= shots_larger_than_player_end + shorts_smaller_than_player_start
    return ans

    number of p