Choosing Study Time 2
InterviewTime limit1sMemory limit512 MB
Given each participant's available time intervals and a fixed study duration T, choose the start time that maximizes the total overlapping attendance time.
- Level
Medium5 of 10
- Topics
- Prefix sum, Intervals, Sorting, Implementation
- Solved
- No attempts yet
Problem
Uichan is gathering participants to run a study group preparing for algorithm contests. Many participants have signed up, but their available times differ, so Uichan is having trouble setting a time for the study group. Uichan is both busy and free, so he wants to run the study group at a time that fits the other participants' schedules as much as possible. When the study group runs for T hours, he wants to compute the participants' time satisfaction and find the time with the maximum time satisfaction.
Time satisfaction is the sum, over the study time, of the time each participant can attend.
For example, suppose the study group is to run for 4 hours and the available times of participants 1, 2, and 3 are as shown in the figure below.
Participant 1 can attend the study group from time 0 to time 6.
Participant 2 can attend the study group from time 1 to time 3 and from time 4 to time 6.
Participant 3 can attend the study group 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 participants can attend the study group, find and print the time with the maximum time satisfaction. If several times have the maximum time satisfaction, print the one with the earliest start time.
Input
The first line gives the number of participants N and the study time T. (1 ≤ N ≤ 1000, 1 ≤ T ≤ 1000)
Starting from the next line, time information for 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 given K does not exceed 5000.
Starting from the second line of each participant's information, K lines give the start time Si and end time Ei of each available interval. Here Ei < Si+1 (1 ≤ i < K). (0 ≤ Si < Ei ≤ 1000)
Output
Find the time with the maximum time satisfaction and print its start time and end time separated by a single space. If several times have the maximum time satisfaction, print the one with the earliest start time.