C - 会議室の混雑 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 366 点

問題文

高橋君は、ある会社の会議室管理システムを開発しています。

この会社には 1 つの大きな会議室があり、N 件の会議の予約が入っています。i 番目の会議は時刻 S_i に開始し、時刻 E_i に終了します。つまり、i 番目の会議は時刻 S_i 以上 E_i 未満の間、会議室を使用しています。

会議室の定員の関係上、同時に K 件以上の会議が重なると問題が発生します。高橋君は、予約のスケジュールに問題がないかを確認したいと思っています。

K 件以上の会議が同時に行われている瞬間が存在するならば Yes を、存在しないならば No を出力してください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 2 \leq K \leq N + 1
  • 0 \leq S_i < E_i \leq 10^9
  • 入力はすべて整数

入力

N K
S_1 E_1
S_2 E_2
:
S_N E_N
  • 1 行目には、会議の件数を表す N 、同時開催の上限を表す K が、スペース区切りで与えられる。
  • 2 行目から N + 1 行目では、各会議の情報が与えられる。
  • 1 + i 行目では、i 番目の会議の開始時刻 S_i と終了時刻 E_i が、スペース区切りで与えられる。

出力

K 件以上の会議が同時に行われている瞬間が存在するならば Yes を、存在しないならば No を 1 行で出力せよ。

入力例 1

3 2
1 5
3 7
6 9

出力例 1

Yes

入力例 2

5 3
0 10
11 20
5 15
21 30
25 35

出力例 2

No

入力例 3

10 4
100 500
200 600
250 400
300 350
700 1000
800 900
850 950
10 50
60 90
500000000 1000000000

出力例 3

Yes

Score : 366 pts

Problem Statement

Takahashi is developing a meeting room management system for a company.

This company has one large meeting room, and N meetings have been reserved. The i-th meeting starts at time S_i and ends at time E_i. In other words, the i-th meeting occupies the meeting room during the time interval from S_i (inclusive) to E_i (exclusive).

Due to the capacity of the meeting room, a problem occurs if K or more meetings overlap at the same time. Takahashi wants to check whether the reservation schedule has any issues.

If there exists a moment when K or more meetings are being held simultaneously, output Yes; otherwise, output No.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 2 \leq K \leq N + 1
  • 0 \leq S_i < E_i \leq 10^9
  • All inputs are integers

Input

N K
S_1 E_1
S_2 E_2
:
S_N E_N
  • The first line contains N, the number of meetings, and K, the upper limit for simultaneous meetings, separated by a space.
  • From the 2nd line to the (N + 1)-th line, the information for each meeting is given.
  • The (1 + i)-th line contains the start time S_i and end time E_i of the i-th meeting, separated by a space.

Output

If there exists a moment when K or more meetings are being held simultaneously, output Yes; otherwise, output No on a single line.

Sample Input 1

3 2
1 5
3 7
6 9

Sample Output 1

Yes

Sample Input 2

5 3
0 10
11 20
5 15
21 30
25 35

Sample Output 2

No

Sample Input 3

10 4
100 500
200 600
250 400
300 350
700 1000
800 900
850 950
10 50
60 90
500000000 1000000000

Sample Output 3

Yes