並び替えの問題を解くアルゴリズムを考える。

n種類の異なる名前にそれぞれ優先順位を表す数字が割り当てられており、その優先順位で並び替える。上からk番目までの名前をすべて求める。ただし数字が同じ場合は、k番目でもk個以上ある可能性はある。また、k+1個以上名前がある時は、そのk+1個の中で優先順位が最小の集合とそれ以外の集合を分けて求める。(priorityは1〜9)

→キーの並び替えと、重なりを数えるという作業が必要。重なりも多いので両方を同時に処理するのがなかなか難しそう

悩んだのですが、こんなのはどうでしょうか？
順番を数えながら配列にいれると、なんかめちゃくちゃ面倒くさい。だから順番は最後まで数えないアルゴリズムならシンプルではないかなと思いました。

phpの正規表現を使って実現します。
まず、
:1:,:2:,:3:,:4:,:5:,:6:,:7:,:8:,:9:,
上のような文字列を用意します。
nameがりんご,priorityが３があったらstr_replaceの関数を使って、":3:,"を":3:,apple,,"に書き換える。
すべてのカラムをこの文字列の中に入れてやる。
そのあとkの数に応じて、こんなパターンを作ってやる。/,(.*?),.*,(.*?) 必要数 ,(.*):(\d):/これでこの配列を取り出してやり、さらに最後の配列に格納されている数字より一つ小さい数字を使って、/:数字:(.*?):/で必要な文字列を取り出し、最後に配列に格納。ここで数を数えてやれば簡単に必要なものを手に入れることができる。

正規表現と数字の大小の比較の計算スピードや配列の数などにも応じてスピードが変わってきそうだが、人が行うような感じで動くのがなにか心地良かった。