 { return v1.second < v2.second || (v1.second == v2.second && v1.first.upper() - v1.first.lower() < v2.first.upper() - v2.first.lower()) || (v1.second == v2.second && v1.first.upper() - v1.first.lower() == v2.first.upper() - v2.first.lower() && v1.first.lower() < v2.first.lower()); }); std::cout << it->first.lower() << ' ' << it->first.upper() << ' ' << it->second << std::endl; return 0;}#include 含めて 25 行](https://image.slidesharecdn.com/iclintroduction-110226064829-phpapp01/85/Brief-introduction-of-Boost-ICL-11-320.jpg)
 { return v1.second < v2.second || (v1.second == v2.second && v1.first.upper() - v1.first.lower() < v2.first.upper() - v2.first.lower()) || (v1.second == v2.second && v1.first.upper() - v1.first.lower() == v2.first.upper() - v2.first.lower() && v1.first.lower() < v2.first.lower()); }); std::cout << it->first.lower() << ' ' << it->first.upper() << ' ' << it->second << std::endl; return 0;}ヘッダのインクルード入力と登録最大値取得出力](https://image.slidesharecdn.com/iclintroduction-110226064829-phpapp01/85/Brief-introduction-of-Boost-ICL-12-320.jpg)
 { return v1.second < v2.second || (v1.second == v2.second && v1.first.upper() - v1.first.lower() < v2.first.upper() - v2.first.lower()) || (v1.second == v2.second && v1.first.upper() - v1.first.lower() == v2.first.upper() - v2.first.lower() && v1.first.lower() < v2.first.lower()); });// 集計値は second// 区間は first (upper(), lower() で境界値)集計された区間の結果を iteration 可能なので普通に max_element で最大値取得](https://image.slidesharecdn.com/iclintroduction-110226064829-phpapp01/85/Brief-introduction-of-Boost-ICL-14-320.jpg)
![Interval Container Library1.46 で導入開区間、閉区間等全部取り扱い可能区間に対する集合演算、「集計」が可能interval_set, interval_map区間の統合方法として join, separate, split を選択可能ストリーム出力有り（例：{(1,3][4.6](7,8]}）Traits 用意すれば自前の interval を突っ込むことも可能数値に限定されないので例えばcotinuous_interval<std::string> w(“a”, “c”) // right_openとか書くと a, b で始まる文字列全部を表すことになる。Example がいっぱいなのでそれ見ればOKinterval_set ainterval_set binterval_set a - b](https://image.slidesharecdn.com/iclintroduction-110226064829-phpapp01/85/Brief-introduction-of-Boost-ICL-15-320.jpg)
Brief introduction of Boost.ICL
- 1. ICL(Interval Container Library)2011/2/26 Boost 勉強会 #4 未発表@yak_ex / 新 康孝紹介詳解
- 2. 自己紹介氏名： 新 康孝 (あたらし やすたか)Twitter ID: yak_exWeb: http://yak3.myhome.cx:8080/junksC++ / Perl が主戦場現在、仕事でコードに触れていないので競技プログラミング（TopCoder、Codeforces）で潤い補充闇の軍団に憧れるただの C++ 好き今回は ICL のさわりだけ、というかさわりしか分からない
- 10. ここで競技コーディングのお時間ですakira さん（仮名）はパーティーを開くことになりました。N 人のお客さんが参加する予定ですが参加時間帯[si, ti)が皆ばらばらです。場所の予約のために参加人数の最も多い時間帯を知りたいのでプログラムを作って akira さんを助けてあげましょう。1 ≦ N ≦ 1000-109 ≦ si < ti ≦ 109,si,ti は整数 (i=1,2,…,N)参加人数が同じ時間帯が隣接している場合、参加者が異なっていても一つの時間帯と見なす同一参加人数の時間帯が複数ある場合は最長の時間帯を、同じ長さの時間帯が複数ある場合は開始時刻がもっとも早い時間帯を返す入力： N<改行>s1<空白>t1<改行>…sN<空白>tN<改行>出力：開始時刻<空白>終了時刻<空白>人数<改行>
- 11. 解答例全文 using ICL#include <iostream>#include <algorithm>#include <utility>#include <boost/icl/interval_map.hpp>int main(void){ boost::icl::interval_map<int, int> sum; int n; std::cin >> n; for(int i = 0; i < n; ++i) { int s, t; std::cin >> s >> t; sum += std::make_pair(boost::icl::interval<int>::right_open(s, t), 1); } typedef boost::icl::interval_map<int, int>::value_type value_type; auto it = max_element(sum.begin(), sum.end(), [](const value_type &v1, const value_type &v2) { return v1.second < v2.second || (v1.second == v2.second && v1.first.upper() - v1.first.lower() < v2.first.upper() - v2.first.lower()) || (v1.second == v2.second && v1.first.upper() - v1.first.lower() == v2.first.upper() - v2.first.lower() && v1.first.lower() < v2.first.lower()); }); std::cout << it->first.lower() << ' ' << it->first.upper() << ' ' << it->second << std::endl; return 0;}#include 含めて 25 行
- 12. 解答例全文 using ICL#include <iostream>#include <algorithm>#include <utility>#include <boost/icl/interval_map.hpp>int main(void){ boost::icl::interval_map<int, int> sum; int n; std::cin >> n; for(int i = 0; i < n; ++i) { int s, t; std::cin >> s >> t; sum += std::make_pair(boost::icl::interval<int>::right_open(s, t), 1); } typedef boost::icl::interval_map<int, int>::value_type value_type; auto it = max_element(sum.begin(), sum.end(), [](const value_type &v1, const value_type &v2) { return v1.second < v2.second || (v1.second == v2.second && v1.first.upper() - v1.first.lower() < v2.first.upper() - v2.first.lower()) || (v1.second == v2.second && v1.first.upper() - v1.first.lower() == v2.first.upper() - v2.first.lower() && v1.first.lower() < v2.first.lower()); }); std::cout << it->first.lower() << ' ' << it->first.upper() << ' ' << it->second << std::endl; return 0;}ヘッダのインクルード入力と登録最大値取得出力
- 13. 解答例 入力と登録 boost::icl::interval_map<int, int> sum; int n; std::cin >> n; for(int i = 0; i < n; ++i) { int s, t; std::cin >> s >> t; sum += std::make_pair(boost::icl::interval<int>::right_open(s, t), 1); }今回は数だが集合も可能右開区間 [s, t)11++11split_interval_map1interval_map21111
- 14. 解答例 最大値取得typedef boost::icl::interval_map<int, int>::value_type value_type; auto it = max_element(sum.begin(), sum.end(), [](const value_type &v1, const value_type &v2) { return v1.second < v2.second || (v1.second == v2.second && v1.first.upper() - v1.first.lower() < v2.first.upper() - v2.first.lower()) || (v1.second == v2.second && v1.first.upper() - v1.first.lower() == v2.first.upper() - v2.first.lower() && v1.first.lower() < v2.first.lower()); });// 集計値は second// 区間は first (upper(), lower() で境界値)集計された区間の結果を iteration 可能なので普通に max_element で最大値取得
- 15. Interval Container Library1.46 で導入開区間、閉区間等全部取り扱い可能区間に対する集合演算、「集計」が可能interval_set, interval_map区間の統合方法として join, separate, split を選択可能ストリーム出力有り（例：{(1,3][4.6](7,8]}）Traits 用意すれば自前の interval を突っ込むことも可能数値に限定されないので例えばcotinuous_interval<std::string> w(“a”, “c”) // right_openとか書くと a, b で始まる文字列全部を表すことになる。Example がいっぱいなのでそれ見ればOKinterval_set ainterval_set binterval_set a - b