So I had a programming competition ,I was stuck in a question and I trying to solve it these few days. because I want to know the answer so much, but I'm not able to do it. Any explanation or answer will be appreciated. Here is the question:

There’s a concert happening at a Hall. The hall is an infinitely long 1D number line, where each of the N students are standing at a certain point in the number line. Since they are all scattered around different positions in the number line, its getting harder to manage them. So the organizer Kyle wants to move them in the hall in such a way so that they all are in consecutive positions, for example, they are in positions 2,3,4,5 instead of being scattered around like 1,3,5,6. In simpler words, there is no gap between them. At one time Kyle can pick one person who is on the most outer positions on any side. For example in 1,3,5,6 the most outer positions are 1 and 6. He can pick either of them and move them to any unoccupied position so that they are not in the most outer position anymore. This makes them come closer and closer with each move until they are all in consecutive positions. Find the maximum and minimum number of moves that can accomplish this task.

CodePudding user response：

I have some idea for you but I'm not totally sure I got it right..

So:

If number 1 is currently the most outer than he is then jumping to the highest number and number 2 is now the outer and it goes infinitely and same goes for the other end the outer on the other side is moving to the next becoming last and so on.. make sense?

CodePudding user response：

The maximum is the count of gaps, since the most inefficient move will reduce the count of gaps between the outermost pair by one.

For the minimum, given k people, in linear time (using a sliding window) find the stretch of k consecutive positions with the most people, and call this count c. Then the minimum is k-c, where each move puts someone from outside this window to inside it.