結果
問題 | No.580 旅館の予約計画 |
ユーザー |
![]() |
提出日時 | 2022-02-12 16:08:22 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 4 ms / 2,000 ms |
コード長 | 1,058 bytes |
コンパイル時間 | 2,159 ms |
コンパイル使用メモリ | 206,064 KB |
最終ジャッジ日時 | 2025-01-27 22:41:27 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 36 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define i64 int64_t #define endl "\n" #define all(a) a.begin(),a.end() #define rep(n) for(int i = 0; i < (n); i++) int overlapping_interval_scheduling_problem(vector<pair<i64, i64>> &tasks, int k) { sort(all(tasks), [](pair<i64, i64> &a, pair<i64, i64> &b) { return a.second < b.second; }); multiset<i64> now; rep (k) now.insert(0); int ret = 0; for (pair<i64, i64> &e: tasks) { auto itr = now.lower_bound(e.first); if (itr != now.begin()) { itr--; ret++; now.erase(itr); now.insert(e.second); } } return ret; } int main() { int n, m; cin >> n >> m; vector<pair<i64, i64>> tasks(m); for (pair<i64, i64> &e: tasks) { i64 ld, rd; string lt_s, rt_s; cin >> ld >> lt_s >> rd >> rt_s; i64 lt = stoi(lt_s.substr(0, 2)) * 60 + stoi(lt_s.substr(3, 2)), rt = stoi(rt_s.substr(0, 2)) * 60 + stoi(rt_s.substr(3, 2)); e = {ld * 1440 + lt, rd * 1440 + rt}; } cout << overlapping_interval_scheduling_problem(tasks, n) << endl; }