老鼠希望能夠知道直播期間最高同時有幾個人在線上觀看,於是他找了會寫程式的你幫忙。
範例測資
範例輸入 | 範例輸出 |
---|---|
第一行 N 代表接下來有 N 個人。 接下來每行有兩個整數 Ai 和 Bi 分別代表這個人進入和離開直播間的時間點。 每個時間點只會有一個人進入/離開 | 請你輸出直播期間最高同時有幾個人在線上觀看。 |
3 1 3 5 6 2 4 | 2 |
解題思路
將「進入時間」跟「出來時間」存在不同的陣列中並「排序」。
跑「進入時間」的 For迴圈,每次人數+1,然後裡面再跑一個「出來時間」的 For迴圈,需要有一個 Start 的變數 (預設為 0),從 Start 這個位置開始判斷,如果出來的時間小於現在的進來時間,那人數就-1,直到跑到出來時間大於進來時間了才把出來時間的 For迴圈 Break 掉,然後在這邊再判斷目前有幾個人的最大值。最後輸出得到的最大值即可。
範例程式碼-ZeroJudge F731: 老鼠的直播間
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
int N;
cin >> N;
vector<int>in;
vector<int>out;
for (int i = 0; i<N; i++)
{
int a, b;
cin >> a >> b;
in.push_back(a);
out.push_back(b);
}
sort(in.begin(), in.end());
sort(out.begin(), out.end());
int people = 0, start = 0, max = -999;
for (int i = 0; i<N; i++)
{
people++;
for (int j = start; j<N; j++)
{
if (out[j] > in[i])
{
start = j;
break;
}
people--;
}
if (people > max) max = people;
}
cout << max << "\n";
}
//ZeroJudge F731
//Dr. SeanXD