Given a set of meals placed on a number line, choose a subset of the meals such that no pair of points are less than distance K away from each other.
Although there are many ways to approach this problem, this editorial will discuss a typical way that someone would reason their way to a solution with problem solving.
In this approach, there is only one observation required.
For any test case, an optimal solution can always take the first meal along the line.
How is it possible to make a statement so bold? Well, consider an optimal solution which does not use the first meal along the line. Then, consider the first meal that the solution does take. We can easily take the first meal along the line instead of taking the meal after it.
This sort of argument is called an exchange argument. Exchange arguments typically come about when you are trying to reason if a greedy algorithm will work for a problem.
In this case, our greedy algorithm is to always take the first meal that we can. From our observation, we can see that this always produces the optimal answer, since the remainder of the street still accessible after taking the first meal is just a smaller version of the same problem, and so we can take the first meal on the smaller version of the problem.
infile = open("distin.txt", "r")
outfile = open("distout.txt", "w")
Ns, Ks = infile.readline().split(" ")
N, K = int(Ns), int(Ks)
d = [int(infile.readline()) for _ in range(N)]
d.sort()
last = -1000000000
ans = 0
for x in d:
if x - last >= K:
last = x
ans += 1
outfile.write(str(ans) + "\n")