If we are allowed to re-order the kids in the line based on priority then there is ALWAYS an optimal solution for any given set of priority list. I am seeing this problem as an application of the "Array Wiggle" problem - where if you can rearrange the kids in a way that you will wiggle an array - then the optimal answer is always (N/2 + N) = 3N/2 for any given arrangement. Any thoughts ?