# #3 Tamdem Bicycle

###### tags:`Greedy Algorithm` `Easy`

## Problem
A tandem bicycle is a bicycle that's operated by two people: person A and person B. Both people pedal the bicycle, but the person that pedals faster dictates the speed of the bicycle. So if person A pedals at a speed of `5`, and person B pedals at a speed of `4`, the tander bicycle moves at a speed of `5` (i.e.. `tandemSpeed = max (speedA, speedB)` ).

You're given two lists of positive integers: one that contains the speeds of riders wearing red shirts and one that contains the speeds of riders wearing blue shirts. Each rider is represented by a single positive integer, which is the speed that they pedal a tandem bicycle at. Both lists have the same length, meaning that there are as many red-shirt riders as there are blue-shirt riders. Your goal is to pair every rider wearing a red shirt with a rider wearing a blue shirt to operate a tandem bicycle.

Write a function that returns the maximum possible total speed or the minimum possible total speed of all of the tandem bicycles being ridden based on an input parameter, `fastest`. If `fastest = true`. your function should return the maximum possible total speed; otherwise it should return the minimum total speed.

"Total speed" is defined as the sum of the speeds of all the tandem bicycles being ridden. For example, if there are 4 riders (2 red-shirt riders and 2 blue-shirt riders) who have speeds of `1, 3, 4, 5`, and if they're paired on tander bicycles as follows: `[1, 4], [5, 3]`, then the total speed of these tandem bicyces is `4 + 5 = 9`.

### Sample Input

redShirtSpeeds = [5, 5, 3, 9, 2]
blueShirtSpeeds = [3, 6, 7, 2, 1]
fastest = true

### Sample Output

32

<br>

:::spoiler **Optimal Space & Time Complexity**

O(nlog(n)) time | O(1) space - where n is the number of tandem bicycles

:::

<br>

:::spoiler Hint 1
Teh brute-force apporach to solve this problem is to generate every possible set of pairs of riders and to determine the total speed that each of these sets generates. This solution does work but, it isn't optimal. Can you think of a better way to solve this problem?
:::

<br>

:::spoiler Hint 2
Try looking at the input arrays in sorted order. How might this help you solve the problem?
:::

<br>

:::spoiler Hint 3
When generating the maximum total speed, you want to pair slowest red-shirt riders with the fatest blue-shirt riders and vice versa, so as to always take advantage of the lagest speeds. When generating the minimun total speed, you wnat to pair the fatest red-shirt rider with the fatest blue-shirt riders, so as to "eliminate" a large speed by pairing it with another large(larger speed).
:::

<br>

:::spoiler Hint 4
Sort the inputs arrays in place, and follow the strategy discussed in Hint 3. With the inputs sorted, you can find the slowest and largest speeds from each shirt color in constant time.
:::

<br>

<hr/>

## Solutions

### Official

覺得這題的解答不太好，因為:
- 用了 `reverseArrayInPlace` 這個部分其實有點冗
- 在取值時其實也可以透過 sort 的安排來讓兩個 array 都取到 `[i]`

function tandemBicycle(redShirtSpeeds, blueShirtSpeeds, fatest) {
    redShirtSpeeds.sort((a, b) => a - b);
    blueShirtSpeeds.sort((a, b) => a - b);
    
    if(!fatest) reverseArrayInPlace(redShirtSpeeds);
    
    let totalSpeed = 0;
    for(let idx = 0; idx < redShirtSpeeds.length; idx++){
        const rider1 = redShirtSpeeds[idx];
        const rider2 = blueShirtSpeeds[blueShirtSpeeds.length - idx - 1];
        totalSpeed += Math.max(rider1, rider2);
    }
    
    return totalSpeed;
}

function reverseArrayInPlace(array) {
    let start = 0;
    let end = array.length - 1;
    while (start < end) {
        const temp = array[start];
        array[start] = array[end];
        array[end] = temp;
        start++;
        end--;
    }
}

<br>

---

### Everyone's

:::spoiler 月

/*
  Time: O(nlogn) | Space: O(1)
*/
function tandemBicycle(redShirtSpeeds, blueShirtSpeeds, fastest) {
  redShirtSpeeds.sort((a,b) => b - a);
  blueShirtSpeeds.sort((a,b) => fastest ? a - b : b - a);
  const { length } = redShirtSpeeds;
  let sum = 0;
  for( let i = 0; i < length; i+=1 ){
    const condition = redShirtSpeeds[i] > blueShirtSpeeds[i];
    sum += condition ? redShirtSpeeds[i] : blueShirtSpeeds[i];
  }
  return sum
}

:::

<br>

:::spoiler 東

// Time O(nlogn) | Space O(1) - n is the number of input redShirtSpeeds
function tandemBicycle(redShirtSpeeds, blueShirtSpeeds, fastest) {
  let result = 0;
  redShirtSpeeds.sort((a, b) => a - b);
  if(fastest) {
      blueShirtSpeeds.sort((a, b) => b - a);
  } else {
      blueShirtSpeeds.sort((a, b) => a - b);
  }

  for(let i = 0; i < redShirtSpeeds.length; i++) {
    result += Math.max(redShirtSpeeds[i], blueShirtSpeeds[i])
  }
  return result;
}

:::

<br>

:::spoiler Hao

/**
 * Time complexity: O(nlogn) where n stands for the length of each list;
 * Space complexity: O(1);
 */


function tandemBicycle(redShirtSpeeds, blueShirtSpeeds, fastest) {
  const sortAscd = (a, b) => a - b;
  redShirtSpeeds.sort(sortAscd);
  blueShirtSpeeds.sort(sortAscd);

  let totalSpeed = 0;
  const nBicycle = redShirtSpeeds.length;

  for (let i = 0; i < nBicycle; i += 1) {
    const [greaterSpeedTeam, minorSpeedTeam] = redShirtSpeeds[0] <= blueShirtSpeeds[0] ? [blueShirtSpeeds, redShirtSpeeds] : [redShirtSpeeds, blueShirtSpeeds];
    minorSpeedTeam.shift();
    totalSpeed += greaterSpeedTeam[fastest ? 'pop' : 'shift']();
  }

  return totalSpeed;
}

:::

<br>

:::spoiler YC

function tandemBicycle(redShirtSpeeds, blueShirtSpeeds, fastest) {

    /*
      time: O(nlogn) - where n is the length of the given array
      space: O(1)
    */

  redShirtSpeeds.sort((a,b)=>a-b)
  blueShirtSpeeds.sort((a,b)=>a-b)
  if(fastest) blueShirtSpeeds.reverse();
  let sum = 0;
  for(let i = 0; i < redShirtSpeeds.length; i++){
    sum += Math.max(redShirtSpeeds[i], blueShirtSpeeds[i])
  }
  return sum;
}

:::

---

## Supplement / Discussion

- 由 Hint 來討論 Greedy Algorithm 為何 apply 在這題

- 我看到的電台的例子
[The set-covering problem (p146-p152)
](https://drive.google.com/file/d/1fV6IdKTPwusJ_ZdwzY5eK5wicgqHA8W3/view?usp=sharing)