http://qiita.com/torazuka/items/cbdb6b581a57e4754dd4
http://d.hatena.ne.jp/torazuka/20140509/yhpg

希望日を出して優先順に振り分けるという、現実でもよくある問題です。
今回は受講対象がひとつで、曜日を分けるだけなのでさほど難しくありません。

<?php
	class LESSON{
	
		/**
		* レッスンを振り分け
		* @param String 「1_12345|2_12345」みたいな文字列
		* @return String 「1_1:2」みたいな文字列
		*/
		public function get($input){
			
			// 入力を分解
			foreach(explode('|', $input) as $val){
				$tmp = explode('_', $val);
				$arr[$tmp[0]] = $tmp[1];
			}
			
			// レッスンを埋める
			$list = $this->fillLesson([], $arr, 0);
			
			// 整形して返す
			ksort($list);
			$list = array_map(function($tmp){
				sort($tmp);
				return implode(':', $tmp);
			}, $list);
			$ret = '';
			foreach($list as $key=>$val){
				$ret .= $key . '_' . $val . '|';
			}
			return substr($ret, 0, -1);
		}
		
		/**
		* レッスンを埋める
		* @param array [希望番号=>[社員]]
		* @param array [社員番号=>希望番号リスト]
		* @param int 第x-1希望
		* @return array $list
		*/
		private function fillLesson($list, $arr, $hope = 0){
			// くるくる
			$nextArr = [];
			foreach($arr as $key=>$val){
				if(!isset($list[$val[$hope]]) || count($list[$val[$hope]]) < 4){
					// 余裕があれば埋める
					$list[$val[$hope]][] = $key;
				}else{
					// 埋まっていれば第二希望に持ち越し
					$nextArr[$key] = $val;
				}
			}
			// 次の希望に持ち越して埋める。希望がなくなれば打ち切り
			if($nextArr && $hope<4){
				return $this->fillLesson($list, $nextArr, $hope+1);
			}
			
			return $list;
		}
		
	}
	
	// 以下はテスト
	$test = [
		['1_12345', '1_1'],
		['30_32451', '3_30'],
		/* 省略 */
	];

	$lesson = new LESSON();
	foreach($test as $key=>$data){
		$answer = $lesson->get($data[0]);
		if($answer !== $data[1]){
			print('えらー');
		}
	}

簡単とか言いながら色々と微妙。
特に整形のあたりはもうちょっとどうにかならなかったものか。
かかった時間は1時間くらい。