루미 알고리즘

#1545플래티넘Meeting

PO 2022 온라인 예선코딩출제 Abdullah Zaghmout영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

A board with N members is planning to have a meeting. Due to the large number of board members, it is difficult to find a time that suits everyone, but the aim is to have as many people as possible attend the meeting.

Each member is available during a number of different time intervals, where each time interval [a, b] means that the member can attend if the meeting starts at some time t where a ≤ t ≤ b. Since some members are very careless with their calendars, the same member may accidentally give you overlapping time intervals, e.g., [1, 3] and [2, 4], even though one interval would have sufficed, in this case [1, 4].

Calculate the maximum number of members who can attend the meeting.

Input

The first line contains an integer N (1 ≤ N ≤ 2 · 10^5), the number of members on the board.

This is followed by N lines, one for each board member. The i-th line starts with the number of time intervals m_i (1 ≤ m_i ≤ 2 · 10^5) during which the i-th member can attend. This is followed by m_i pairs of integers, one for each interval. These pairs a, b (0 ≤ a ≤ b ≤ 10^9) represent the interval [a, b].

Let B=∑_{i=1}^N m_i be the sum of the number of time intervals during which all members are available. It is given that B ≤ 2 · 10^5.

Output

Print a single line with an integer – the maximum number of members that can attend the meeting if the start time is chosen optimally.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.

GroupPointsConstraints
110B ≤ 100 and 0 ≤ a ≤ b ≤ 100
215B ≤ 1,000, and 0 ≤ a ≤ b ≤ 4,000, and no single member has two overlapping time intervals
330No single member has two overlapping time intervals
415B ≤ 1,000 and 0 ≤ a ≤ b ≤ 4,000
530No additional constraints.

Explanation of Samples

In the first example, we can choose to start the meeting at time 4, when members 2 and 3 can attend. This case could be included in all test case groups.

Examples 2 and 3 could not be included in test case groups 2 or 3.

예제

예제 1

입력
3
2 1 3 5 6
4 1 10 11 12 17 18 14 15
1 4 4
출력
2

예제 2

입력
3
3 2 8 2 7 5 6
4 7 15 15 20 9 13 18 20
3 12 19 9 16 12 16
출력
2

예제 3

입력
3
2 5 14 0 20
3 5 16 5 11 8 9
2 7 11 7 18
출력
3

출처 표기

출처: Programmeringsolympiaden 2022년 온라인 예선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.