### PROBLEM LINKS

### DIFFICULTY

MEDIUM

### EXPLANATION

Assume, without loss of generality, that C_{1}≤C_{2} (otherwise swap them). There are 2 cases to consider.

If there are more than M available problems with difficulty ratings between C_{1} and C_{2}, inclusive, then all problems with a difficulty rating less than C_{1} or greater than C_{2} can be ignored. Now, we can decide, given a maximum difficulty gap G, if it’s possible to select M problems such that the difficutly gap does not exceed G in O(N) time (assuming the difficulty ratings have been sorted ahead of time). To accomplish this, we use a greedy method where we select P_{1} as the problem with the highest difficulty rating not exceeding C_{1}+G, then Pias the problem with the highest difficulty rating not exceeding P_{i-1}+G for 1 < i ≤ M. If P_{m} ≥ C_{2}, then there is a solution. The minimum value of G can be found using binary search.

If there are at most M available problems with difficulty ratings between C_{1} and C_{2}, then we choose all of them. The remaining problems are chosen greedily, always choosing the problem that produces the smallest difficulty gap between itself and the nearest already chosen problem.

### SETTER’S SOLUTION

Can be found here.

### TESTER’S SOLUTION

Can be found here.