Problem 350714 · hard · Level 03 Linear Management & Searching

Two Tasters Who Disagree

sorting · multi-key sort · merge sort · inversions

Two tasters scored the same dishes: dishes[i] = (a, b) means taster A gave dish i the score a and taster B gave it b. Two dishes are a clash if the tasters strictly disagree about them: A scores one dish strictly higher, while B scores that same dish strictly lower. If either taster gave the two dishes equal scores, they do not clash. Return the number of unordered pairs of dishes that clash.

Examples

Input:  dishes = [(1, 3), (2, 2), (3, 1)]
Output: 3
Explanation: every pair is ranked in opposite orders by the two tasters.

Input:  dishes = [(1, 1), (1, 0), (2, 0)]
Output: 1
Explanation: only dishes 0 and 2 clash; the other pairs share a score from one taster.

Constraints

  • 0 <= len(dishes) <= 5 * 10**4
  • 0 <= a, b <= 10**9
  • Target complexity: O(n log n). Comparing every pair is too slow for the largest inputs.

Goals

  • Turn a two-score comparison into counting out-of-order pairs in one list
  • Choose the secondary sort key so that ties are never counted
  • Count strict inversions with merge sort in O(n log n)
Starting Python…