ZeroJudge F731: 老鼠的直播間

老鼠希望能夠知道直播期間最高同時有幾個人在線上觀看,於是他找了會寫程式的你幫忙。

範例測資

範例輸入範例輸出
第一行 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

發佈留言