[演算法題目] Class Photos

本題資訊

難度：easy
使用語言：C++
相關概念：Greedy Algorithm

題目敘述

It’s photo day at the local school, and you’re the photographer assigned to take class photos. The class that you’ll be photographing has an even number of students, and all these students are wearing red or blue shirts. In fact, exactly half of the class is wearing red shirts, and the other half is wearing blue shirts. You’re responsible for arranging the students in two rows before taking the photo. Each row should contain the same number of the students and should adhere to the following guidelines:

All students wearing red shirts must be in the same row.
All students wearing blue shirts must be in the same row.
Each student in the back row must be strictly taller than the student directly in front of them in the front row.

You’re given two input arrays: one containing the heights of all the students with red shirts and another one containing the heights of all the students with blue shirts. These arrays will always have the same length, and each height will be a positive integer. Write a function that returns whether or not a class photo that follows the stated guidelines can be taken.

Note: you can assume that each class has at least 2 students.

Sample Input:

redShirtHeights = [5, 8, 1, 3, 4]
blueShirtHeights = [6, 9, 2, 4, 5]

Sample Output:

true

也是一題文字敘述頗長的題目。

簡而言之，有個班級要拍照，而我手邊有兩組人馬的身高數據（都是整數），一組穿紅色衣服，一組穿藍色衣服。穿同樣顏色衣服的人必須要在同一排，而且後面的一定要比前面的還要高，不能被前面的人擋住（不能一樣高）。

我們需要寫個函式判斷目前的隊伍是否有符合條件。

Idea 1 (錯誤示範)

因為後面隊伍總是比前排高，我的想法是一開始可以由第一個元素判斷誰前誰後，再來逐一比較大小關係是否相符。結果測試結果是錯了……因為題目的意思是我可以重新安排隊伍，而不是固定順序。

而且我兩段程式碼會重複，雖然不影響時間，但很冗長也不好讀。

/*這是錯的!!!! It's wrong!!!*/
#include <vector>
using namespace std;

bool classPhotos(vector<int> redShirtHeights, vector<int> blueShirtHeights) {
  if (redShirtHeights[0] > blueShirtHeights[0]){
    for (int i = 1; i < redShirtHeights.size(); i++){
      if (redShirtHeights[i] <= blueShirtHeights[i]){
        return false;
      }
    }
    return true;
  } else {
    for (int i = 1; i < redShirtHeights.size(); i++){
      if (redShirtHeights[i] >= blueShirtHeights[i]){
        return false;
      }
    }
    return true;
  }
  return false;
}

Idea 2

既然順序是可以變動的，很顯然最好先透過排序再操作。

順序排好後，可以透過逐一比對是否同列每個同學都一致高於或矮過另一列同學。這裡我們以紅色隊伍的視角，把紅色隊伍高過藍色隊伍的人數紀錄在 greater 中，藍色隊伍高過紅色隊伍紀錄在 lower 中，若有任何一個數是相等於紅色隊伍人數，那就表示一致高或矮於藍色隊伍。

#include <vector>
using namespace std;

bool classPhotos(vector<int> redShirtHeights, vector<int> blueShirtHeights) {
  sort(redShirtHeights.begin(), redShirtHeights.end());
  sort(blueShirtHeights.begin(), blueShirtHeights.end());

  int greater = 0;
  int lower = 0;
  int n = redShirtHeights.size();

  for (int i = 0; i < n; i++){
    if (blueShirtHeights[i] < redShirtHeights[i])
      greater++;
    else if (redShirtHeights[i] < blueShirtHeights[i])
      lower++;
  }
  return greater==n || lower==n;
}

時間複雜度：\(O(n\log n)\)，\(n\) 是一列隊伍長度。
空間複雜度：\(O(1)\)

Idea 3

另外因為是逐一比對看大小一致性，我們也可以利用相乘的性質操作。首先將兩個隊伍的第一個人相減後的結果存在 check 內，並跑個迴圈逐一身高相減（相減的順序要一樣，例如維持紅色減藍色），並和 check 相乘。如果結果大於 0，表示兩邊是同號，具有一致性；如果小於等於 0，則不具有一致性或是有身高相等的狀況，直接回傳 false。

#include <vector>
using namespace std;

bool classPhotos(vector<int> redShirtHeights, vector<int> blueShirtHeights) {
  sort(redShirtHeights.begin(), redShirtHeights.end());
  sort(blueShirtHeights.begin(), blueShirtHeights.end());
  int n = redShirtHeights.size();
  int check = redShirtHeights[0] - blueShirtHeights[0];

  for (int i = 0; i < n; i++){
    if ((redShirtHeights[i] - blueShirtHeights[i]) * check <= 0)
      return false;
  }
  return true;
}

時間複雜度：\(O(n\log n)\)，\(n\) 是一列隊伍長度。
空間複雜度：\(O(1)\)