読者です 読者をやめる 読者になる 読者になる

C Sharpens you up

http://qiita.com/yuba に移しつつあります

コーディング課題・貸しボート屋の問題

CodeIQの問題・パズルを考えよう!(by CodeIQ×はてな

ある湖の貸しボート屋が古いボートを処分しようとしましたが何艘残せばいいかわかりません。
貸し出しリストから、ピークのときに何艘が貸し出されていたかを求めたいです。

貸し出しリストは

貸出日時, 返却日時, ボート番号

の組になっており、貸出日時の順に並んでいます。

このリストを一回だけスキャンして(ランダムアクセスすることなく)ピーク貸出数を算出してください。(2013-08-25 制約が曖昧だったので書き直しました)
このリストからピーク貸出数を算出してください。
リストは膨大なサイズなのでメモリに収まることは期待できません。1回のシーケンシャルアクセスで解決してください(ボートの数はたかが知れているので、ボートの数に比例する程度のメモリを使うことは問題ありません)。

ただし、同一時刻に返却と貸出があった場合、それらの貸出期間は重なっていないものとします。

例えば

('2013-08-22 08:00', '2013-08-22 09:00', 5)
('2013-08-22 08:30', '2013-08-22 09:30', 6)
('2013-08-22 09:00', '2013-08-22 09:30', 7)

という貸出記録だったら2が回答です。

応用問題

貸出リストは

CREATE TABLE rental (
  rental_id INT NOT NULL PRIMARY KEY,
  starts DATETIME NOT NULL,
  ends DATETIME NOT NULL,
  boat_id INT NOT NULL
);

というRDBテーブルになっています。

ピーク数をSELECT文一本で算出してください。