Last Updated: 28 May, 2025
Same Score
Easy
Asked in company
You are given 'N' pairs of integers representing the scores of Bob and Noddy at different points during their rugby match. Each pair ( A[i], B[i] ) represents Bob's score and Noddy's score respectively at the i-th observation.
Find the maximum possible number of times Bob and Noddy could have had equal scores (ties) during the entire match, assuming they started from (0, 0).
For Example :
Let N = 3, and the score pairs be: (1, 2), (3, 2), (3, 4).
One possible sequence of goals could be:
(0,0) -> (1,0) -> (1,1) -> (1,2) -> (2,2) -> (3,2) -> (3,3) -> (3,4)
The ties occur at: (0,0), (1,1), (2,2), (3,3) = 4 times.
Therefore, the answer is '4'.
Input Format :
The first line contains an integer 'N'.
The next 'N' lines each contain two integers, representing Bob's and Noddy's scores.
Output Format :
Return the maximum possible number of ties between Bob and Noddy's scores.
Note :
You don't need to print anything. Just implement the given function.
Constraints :
1 <= N <= 10^5
0 <= A[i], B[i] <= 10^9
All score pairs are given in non-decreasing order
The last score pair denotes the final score of both players.
Time Limit: 1 sec
Approaches
Approach:
- Iterate through consecutive score observations.
- For each interval, find the range of possible new tie scores.
- The lower bound is the next integer after the last recorded tie and at least the maximum of the previous scores.
- The upper bound is the minimum of the current scores.
- The number of integers in this range contributes to the total ties.
- Sum up all possible ties across all observations, including the initial tie at (0,0).
Algorithm:
- Initialize a variable total_ties to 1.
- Initialize a variable last_tie_score to 0.
- Initialize variables prev_a and prev_b to 0, representing the starting scores.
- Iterate through the given n score pairs using an index i from 0 to n - 1:
- Let curr_a be Bob's score (A[i]) and curr_b be Noddy's score (B[i]) for the current observation.
- Calculate the starting possible tie score start_x as the maximum of (last_tie_score + 1) and max(prev_a, prev_b).
- Calculate the ending possible tie score end_x as min(curr_a, curr_b).
- If start_x is less than or equal to end_x
- Add 'end_x - start_x + 1' to total_ties.
- Update last_tie_score to end_x, as this is the highest tie score reached in this interval.
- Update prev_a to curr_a and prev_b to curr_b for the next iteration.
- Return total_ties.