選んだビーンズの色が \(c\) であるとします。このとき、考えられるおいしさの最小値は色が \(c\) であるビーンズの中でのおいしさの最小値です。

つまり、この問題ではすべての色についてその色を選んだ時に考えられるおいしさの最小値を求め、すべての色のうちこの値が最も大きいものを求める必要があります。

各色について、\(N\) 種類すべてのビーンズを確認することで正しい答えを得られますが、色の種類数も最大で \(N\) 種類あるため、これを愚直に実装すると\(O(N^{2})\) 時間かかってしまい実行時間制限超過してしまいます。

この問題では、連想配列 (C++では std::map, std::unordered_map 、Pythonではdict,deafaultdictなど) を用いて、各色のおいしさの最小値を管理することで \(O(N\log{N})\) や expected \(O(N)\) などの時間で実行できます。 具体的には、各ビーンズを順番に見て行き、連想配列にそのビーンズの色の添字が存在する場合はおいしさの最小値を更新し、そうでない場合は新しく色の添字を追加して最小値をそのビーンズのおいしさとすることで最終的に各色のビーンズのおいしさの最小値が求まります。

詳細は実装例を参考にしてください。

実装例(C++):

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n;
  cin >> n;

  map<int, int> minimum_taste; // 各色のおいしさの最小値
  for (int i = 0; i < n; ++i) {
    int a, c;
    cin >> a >> c;
    if (minimum_taste.contains(c)) {
      // すでに色cが存在している場合は最小値を更新
      minimum_taste[c] = min(minimum_taste[c], a);
    } else {
      // 新しく追加される色
      minimum_taste[c] = a;
    }
  }

  int ans = -1;
  // 存在する色をすべて走査する
  for (auto [c, val] : minimum_taste){
    ans = max(ans, val);
  }

  cout << ans << endl;
}