Tandem Bicycle

Tags

Tandem Bicycle

Category

Greedy

Difficulty

Easy

Problem Statement

A tandem bicycle is ridden by two people, and its speed is determined by the faster rider. Given two arrays of positive integers representing the speeds of riders in two groups, pair each rider from the first group with a rider from the second group. Find the maximum (or minimum) possible total speed across all tandem bicycles.

Intuition

Each tandem bicycle's speed is max(rider1, rider2). To maximize total speed, we want fast riders to not "waste" their speed by being paired with other fast riders. Pairing the fastest with the slowest ensures that each fast rider contributes their speed independently. Conversely, to minimize total speed, we pair the fastest with the fastest so that fast riders overlap and their combined contribution is minimized.

Approach

For maximum total speed:

  1. Sort one group in ascending order and the other in descending order.
  2. Pair the i-th element from each sorted array.
  3. Sum up max(pair) for all pairs.

For minimum total speed:

  1. Sort both groups in ascending order.
  2. Pair the i-th element from each sorted array.
  3. Sum up max(pair) for all pairs.

Pseudocode

function tandemBicycle(redSpeeds, blueSpeeds, fastest):
    sort(redSpeeds)

    if fastest:
        sort(blueSpeeds, descending)
    else:
        sort(blueSpeeds, ascending)

    totalSpeed = 0
    for i from 0 to length(redSpeeds) - 1:
        totalSpeed = totalSpeed + max(redSpeeds[i], blueSpeeds[i])

    return totalSpeed

Time & Space Complexity

  • Time: O(n log n) for sorting both arrays, where n is the number of riders in each group.
  • Space: O(1) if sorting is done in-place.

Key Insights

  • The speed of a tandem bicycle is determined solely by the faster rider; the slower rider's speed is irrelevant.
  • For maximum: pairing fast with slow ensures each fast person's speed is counted. Pairing two fast people wastes one of their speeds.
  • For minimum: pairing fast with fast lets one fast rider "absorb" another, reducing the total.
  • This is a classic greedy problem where sorting and strategic pairing yield the optimal solution.

Edge Cases

  • All riders have the same speed: total speed is n * speed regardless of pairing strategy.
  • Groups of size 1: total speed is simply max(rider1, rider2).
  • One group has all very fast riders and the other all slow: maximizing pairs each fast with slow, minimizing pairs fast with fast where possible (but in this case, results are the same since the fast group dominates).

Linked mentions