for whoever taking a look

fyi fastest (time complexity) solution is O(m+n)
takes O(r) in space (r being max range for the shots, here 10^5)

no sort (O(nlogn+mlogm)) needed
no search (O(mlogn) or O(nlogm)) needed

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

First off, don't worry if you don't know cricket. The fundamental problem here deals with range-overlap, and the two sets (shots & fielding-ranges) are equivalent data structures. Choose one range (shots or fielding arbitrary, which one). This will be a bunch of starting and end data, likely with a lot of overlap. Let's say that we're dealing with the "shots" data. We can give each "shot" range a score based on the number of "fielding" ranges that it overlaps with. Our final score would be the sum of all of the "shot" scores. (You can start with the fielding-ranges and compare those against the shots as well; whichever way you choose will yield the same score at the end.

Similar to previous challenges, we can aggregate our data by incrementing indices each time a range starts at that index, and de-incrementing the position after the final position in a range. We can process through this data structure and keep track of how many ranges are active at any given time by keeping a running sum of increments and deincrements, as ranges start and stop, and for this purpose, we are interested in any position where the NET number of active ranges changes.

We will need TWO of these data-structures. One for the "shots" range-data and the other for the "players" range-data.

For SCORING, we are interested in any position where a range begins, even if the net number of active zones doesn't change. Why? Imagine that we are evaluating "shots", and in a given shot's range, there are three corresponding fielding ranges which run consecutively, such that each time that one fielding range stops, the next picks up at the next index. The total number of active ranges remains the same throughout, but our shot gets credit for all three.

So we evaluate scoring at a given index if one, or the other, or both data-structures have a range that starts at that index; If there is a drop-off, we still need to update our rolling count of active ranges, but our score can only increase if either a "shots" range or a "player" range begins at the index.

Scoring is a little tricky. Every time that a range begins in either data-structure, we give it credit for the number of active ranges in the opposing data-structure. But what if BOTH shots and fielding data-structures have ranges that begin at the same index? Here, it's important to seperate out the new increments from the ranges that were already active. So say we had 3 existing "shots" ranges, and at index "i" 2 new ones come online, and one drops off, bringing the total number of active ranges to (3 + 2 - 1 = 4). At that same index, we had 2 existing player-ranges, had 1 come on and 1 drop off, leaving us with the same number of player ranges (2 + 1 - 1 = 2). The 2 new shot ranges increment the score by the number of previously existing player ranges that are still active (1), so we increment our score by 2 to account for this contribution. The 2 new shot ranges also increment the score by the number of new player ranges that have come online (1), so we increment our score again by 2. So we see that to account for adding two new ranges in our "shots" data-structure we have incremented our score by (number of shots increments * number of active player ranges = 2 * 2 = 4), which we have to do any time we increment an index in shots, but what about the new range in player-shots? We've accounted for the new additions in shots, but what the two pre-existing ranges that didn't drop off? We have to give them credit for the new additions in the player-range data, so we add another (2 * 1 = 2), meaning that in total we've added 6 to our score.

Clear as mud? Yeah, probably, but maybe this helped somebody.

As far as implementation: Since we have to use something that can hold both the "increment" and "deincrement" data at each index, I found it useful to use a TreeSet with "roll your own"some nodes that hold the required data anlong with an index for comparative sorting. That allowed me to only maintain data positions of interest instead of instantiating an array to hold every position, and also helped while iterating through the data-structure as gaps in the index-set could be skipped over. I would anticipate the "fuller" the index-set becomes, the more this implentation (O(log(n) seek) will be less efficient than an Array-backed structure with a constant seek time, since as your index-set approaches "n", you're going to be evaluating every index anyway.

The wording is very confusing for those who don't play cricket TBH. What is a "1D plane"? I thought planes are always 2D. What does it mean to "field a shot"? How "favorite shot" is different from the other ones?

Also, the "overlap" illustration fails to show the only non-trivial case: when segments overlap in one point, e.g. [1,2] and [2,3]. Juding by the example this is considered an "overlap", but it is not clear from the description.

I solved it this way with Python: 1. put all the numbers in one sorted array followed the rule that the start of the range must be before the end of the range at the same point. For that I converted int to float and for the start of the range I deducted 0.2 for players and 0.1 for shots, and for the end added. 2. loop through that array def solve(shots, players): # Write your code here cur_shots, cur_players, strenths = 0, 0, 0 arr_pl_sh = [] for i in range(len(players)): arr_pl_sh.append(float(players[i][0]) - 0.2) arr_pl_sh.append(float(players[i][1]) + 0.2) for i in range(len(shots)): arr_pl_sh.append(float(shots[i][0]) - 0.1) arr_pl_sh.append(float(shots[i][1]) + 0.1) arr_pl_sh.sort() for x in arr_pl_sh: if (str(x)[-1] == "8"): cur_players += 1 strenths += cur_shots elif (str(x)[-1] == "9"): cur_shots += 1 strenths += cur_players elif (str(x)[-1] == "2"): cur_players -= 1 elif (str(x)[-1] == "1"): cur_shots -= 1 return strenths