有一組數據是在客人到達和出發時間，問：多少把椅子的能力，以滿足所有客人的需求，可以有一個地方坐下要求。

有些人甚至開始考慮暴力法，這些數據是少，其實這個問題很多數據， 暴力需求O(n*n)的時間效率，顯然，將加班，因此，有必要O(n) 或O(nlgn)算法。

屬于一道想透了就很easy的，可是沒想過就會很困難的題目。

解法是：

把全部客人到來和離開的時間都排成序列。每次客人到來須要n張桌椅，那么就+上n，每次客人離開就會返還n張桌椅，那么就-去n，求這種最大值。

詳細算法代碼就那么幾行，處理IO的代碼都比這個長。

要想出來還真是十分困難。只是也算是經典算法了，應該學熟練。

const int MAX_N = 10001; struct Interval {int t, wei;bool operator<(Interval const &i) const{if (t == i.t) return wei < i.wei;return t < i.t;} };Interval inter[MAX_N<<1];inline int timeToSec(int h, int m) {return h * 60 + m; }int main() {int T, n, h, m, w, num;scanf("%d", &T);while (T--){scanf("%d", &n);num = 0;for (int i = 0; i < n; i++){scanf("%d %d:%d", &w, &h, &m);inter[num].t = timeToSec(h, m);inter[num++].wei = w;scanf("%d:%d", &h, &m);inter[num].t = timeToSec(h, m);inter[num++].wei = -w;}sort(inter, inter+num);int ans = 0, tmp = 0;for (int i = 0; i < num; i++){tmp += inter[i].wei;ans = max(tmp, ans);}printf("%d\n", ans);}return 0; }

轉載于:https://www.cnblogs.com/yxwkf/p/4602012.html

總結

以上是生活随笔為你收集整理的HDU 4883 Best Coder Round 2 TIANKENG’s restaurant 解读的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。