Choosing Study Time 1
Time limit1sMemory limit512 MB
Given each participant's available time intervals and a fixed study duration T, find the length-T slot maximizing total overlap time across all participants, breaking ties by earliest start.
- Level
Medium7 of 10
- Topics
- Prefix sum, Sliding window, Intervals, Sorting
- Solved
- No attempts yet
Problem
Uichan is gathering several participants to run a study group for an algorithm contest. Many participants have signed up, but their available times differ, so Uichan has trouble deciding when to hold the study sessions. Uichan is busy yet free, so he wants to schedule the study sessions to fit the other participants' times as much as possible. When the study group runs for T hours, he wants to compute the participants' time satisfaction and find the time slot with the maximum time satisfaction.
The time satisfaction is the sum, over the study time, of the time each participant can take part.
For example, suppose the study group will run for 4 hours and participants 1, 2, and 3 have the available times shown in the figure below.
Participant 1 can study from time 0 to time 6.
Participant 2 can study from time 1 to time 3 and from time 4 to time 6.
Participant 3 can study from time 4 to time 8.
If the study group runs from time 2 to time 6, the time satisfaction is 4 + (1 + 2) + 2 = 9, which is the maximum time satisfaction.
Given the times at which the participants can join the study group, find and output the time slot with the maximum time satisfaction. If several time slots have the maximum time satisfaction, output the one with the earliest start time.
Input
The first line gives the number of participants N and the study duration T. (1 ≤ N ≤ 100,000, 1 ≤ T ≤ 100,000)
Starting from the next line, the time information of the N participants is given.
The first line of each participant's information gives the number of available intervals K. K is a positive integer, and the sum of all K values in the input does not exceed 500,000.
From the second line of each participant's information, K lines follow, each giving the start time Si and the end time Ei of an available interval. Here Ei < Si+1 (1 ≤ i < K). (0 ≤ Si < Ei ≤ 100,000)
Output
Find the time slot with the maximum time satisfaction and output its start time and end time separated by a single space. If several time slots have the maximum time satisfaction, output the one with the earliest start time.