Amplitude Hackathon Summer '24 Problem 6 - Kurt's Coffee Cabal

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 1G

Problem type

Have you had coffee with Kurt recently? Maybe you should.

Coffee with Kurt is very simple. n of Kurt's friends tell Kurt when they're available, and Kurt schedules coffee for a single interval of time.

Kurt doesn't want to drink coffee by himself though, so he will only schedule an interval of time where, at every instant in time inside the given interval, at least k of Kurt's friends will be free to drink coffee with him. Note that people are welcome to leave and join depending on their availability, Kurt just needs at least k people at all points in time, otherwise he will get lonely.

For each possible value of k from 1 to n, help Kurt find the longest interval of time he can schedule coffee for.

Constraints

1 \le n \le 10^5

1 \le s_i \le t_i \le 10^9

Subtask 1 [1 point]

1 \le n \le 50

Subtask 2 [1 point]

No additional constraints.

Input Specification

The first line contains a single integer, n.

The next n lines each contain two integers, s_i and t_i, indicating that friend i is free from time s_i to time t_i inclusive.

Output Specification

Output n integers. The i^\texttt{th} integer should be the maximum length of the longest interval that Kurt can schedule coffee for given he wants to get coffee with i people. If it is not possible to get coffee with at least i people, output 0.

Sample Input 1

3
1 39
17 1000
1001 1002

Sample Output 1

999 22 0

Sample Explanation 1

If Kurt schedules coffee from time 1 to time 1000, he can get coffee with at least one friend at every point of time within. If Kurt schedules coffee from time 17 to time 39, he can get coffee with both the first and second friend. It is not possible for him to get coffee with all three friends simultaneously - there will not be anyone in the time range (1000, 1001) available for Kurt to get coffee with.


Comments

There are no comments at the moment.