C - Meeting Reservation Management Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

高橋君は会社の会議予約管理システムを開発しています。

この会社では、1 日を T 分間として運営しており、時刻 0 から時刻 T までの時間帯で会議の予約を受け付けています。それぞれの会議には開始時刻と終了時刻が設定されています。

高橋君は、予約の重なり具合を数値化したいと考えました。具体的には、ある瞬間に同時に行われている会議の件数の最大値を求めたいです。

N 件の会議の予約があり、i 番目 (1 \leq i \leq N) の予約は時刻 S_i に開始し、時刻 E_i に終了します。会議は開始時刻を含み、終了時刻を含みません。すなわち、i 番目の会議が行われている時間帯は半開区間 [S_i, E_i) です。

ある時刻 t において、S_i \leq t < E_i を満たす予約の数を、その時刻の「同時利用数」と呼びます。

0 \leq t < T を満たすすべての実数 t における同時利用数の最大値を求めてください。

なお、異なる予約の開始時刻や終了時刻が互いに一致することや、まったく同じ時間帯の予約が複数存在することもあり得ます。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq T \leq 10^9
  • 0 \leq S_i < E_i \leq T (1 \leq i \leq N)
  • 入力はすべて整数

入力

N T
S_1 E_1
S_2 E_2
\vdots
S_N E_N
  • 1 行目には、予約の件数を表す整数 N と、1 日の長さ（分）を表す整数 T が、スペース区切りで与えられる。
  • 続く N 行のうち i 行目 (1 \leq i \leq N) には、i 番目の予約の開始時刻 S_i と終了時刻 E_i がスペース区切りで与えられる。

出力

0 \leq t < T を満たすすべての時刻における同時利用数の最大値を 1 行で出力せよ。

入力例 1

3 60
10 30
20 40
35 50

出力例 1

2

入力例 2

5 480
0 120
60 180
90 150
200 300
200 400

出力例 2

3

入力例 3

8 1000000000
100 500000000
100 999999999
200 300
200 400
200 500
999999000 1000000000
0 1000000000
50 150

出力例 3

6

Score : 366 pts

Problem Statement

Takahashi is developing a meeting reservation management system for his company.

This company operates with a day lasting T minutes, and accepts meeting reservations during the time period from time 0 to time T. Each meeting has a designated start time and end time.

Takahashi wants to quantify the degree of reservation overlap. Specifically, he wants to find the maximum number of meetings taking place simultaneously at any given moment.

There are N meeting reservations, and the i-th reservation (1 \leq i \leq N) starts at time S_i and ends at time E_i. A meeting includes its start time but excludes its end time. That is, the time interval during which the i-th meeting takes place is the half-open interval [S_i, E_i).

At a given time t, the number of reservations satisfying S_i \leq t < E_i is called the "concurrent usage count" at that time.

Find the maximum concurrent usage count over all real numbers t satisfying 0 \leq t < T.

Note that different reservations may share the same start times or end times, and there may be multiple reservations with exactly the same time interval.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq T \leq 10^9
  • 0 \leq S_i < E_i \leq T (1 \leq i \leq N)
  • All input values are integers

Input

N T
S_1 E_1
S_2 E_2
\vdots
S_N E_N
  • The first line contains an integer N representing the number of reservations and an integer T representing the length of a day (in minutes), separated by a space.
  • The following N lines each contain, on the i-th line (1 \leq i \leq N), the start time S_i and end time E_i of the i-th reservation, separated by a space.

Output

Output in a single line the maximum concurrent usage count over all times t satisfying 0 \leq t < T.

Sample Input 1

3 60
10 30
20 40
35 50

Sample Output 1

2

Sample Input 2

5 480
0 120
60 180
90 150
200 300
200 400

Sample Output 2

3

Sample Input 3

8 1000000000
100 500000000
100 999999999
200 300
200 400
200 500
999999000 1000000000
0 1000000000
50 150

Sample Output 3

6