Don't Be Fake
InterviewTime limit1sMemory limit1024 MB
Given each friend's available second intervals, find the maximum number of friends who can photograph one notification second and count the seconds that reach it.
- Level
Easy3 of 10
- Topics
- Prefix sum, Array
- Solved
- No attempts yet
Problem
DontBeFake is an app that sends each user a notification at a random moment. The user then has to photograph what they are doing at that exact moment.
You have friends on DontBeFake. Each friend has a set of time intervals when they are available. If a friend gets a notification at second and falls inside one of their available intervals, they take a picture, and you get to view it. The app and taking a picture are both slow, so a friend who becomes available only one second after does not have time to take the picture.
All friends live in the same time zone and get one notification at exactly the same time of day. All times are seconds from midnight.
Find the maximum number of pictures you can view in the day, over all seconds when the notification can arrive. Also find how many different seconds the notification could arrive at so that the maximum number of pictures is taken.
Input
The first line contains an integer (). Each of the next lines describes the available intervals of one friend. Each such line starts with an integer (), followed by pairs of integers , (). This means the friend is available from second to second , inclusive.
It is guaranteed that for all , so the intervals do not overlap. It is also guaranteed that .
Output
On the first line, print the maximum number of pictures you can view in the day. On the second line, print the total number of seconds at which the notification could arrive for the maximum number of pictures to be taken.