# [Alarms](https://open.kattis.com/problems/alarms) editorial

## Subtask 1: $K=N$

In this subtask, we have to choose every alarm. Thus, it suffices to simply find the largest distance between two ring times. This can be done by first sorting all times, and then checking for the largest distance between adjacent times.

## Subtask 3/4

Main idea: There are too many ways to choose $K$ alarms, so let's instead focus on what interval we can choose as the longest undisturbed one. For a given interval, it can be undisturbed if there are at most $N-K$ different alarms that ring in it. Also note that there is no point in considering times other than the ones given in the input, so there are only $O(N^2)$ intervals to consider.

We now get a new problem: Given a list of numbers, find the longest interval with at most $N-K$ distinct numbers in it.

To get subtask $3$, try all intervals and check each one.

To solve it faster than that, we can use two-pointers. For a fixed right endpoint $R$, find the leftmost $L$ such that $(L,R)$ contains at most $N-K$ different numbers. As $R$ moves to the right, increase $L$ until the number of different numbers is small enough. To keep track of how many distinct elements we have in our current interval, we can use a very simple but surprisingly powerful technique: a frequency array `freq[alarm]` that counts how many occurrences of each alarm we have. This can be easily updated in $O(1)$ and also allows us to keep track of the number of distinct alarms.

The time complexity is $O(N\log(N))$ because we need to sort all the ring times, but after sorting it is $O(N)$.