n O(n log n) time and finds the longest sequence of moves. Do not write the code, give steps and methods. Explain the steps of algorithm, and the logic behind these steps in plain English In some initial states, has no valid moves.
Given n distinct integers on an array and a positive integer K.
step1. choose any two integers x and y in the array which differ by at most K, i.e. |x − y| ≤ K.
step2. remove the smaller of the two chosen integers.
one move is consisting of the two steps above.
task is to make moves in this way until no longer able to do so.
in some cases, may be unable to make even a single move.
Design an
Do not write the code, give steps and methods. Explain the steps of algorithm, and the logic behind these steps in plain English
In some initial states, has no valid moves. For example, if n = 5, K = 1 and the numbers are 1, 3, 5, 7, 9, then cannot make any moves and the longest sequence of moves is simply the empty sequence.
Use the greedy method.
Step by step
Solved in 2 steps
