I think priority queue can do this

It's a wiggle sort question and can be solved in 4-line c++ codes. You probably need to check more leetcode questions.

Greedy approach works here. Its a simple O(N) solution. Just swap the adjacent numbers if they don't follow the given rule. Eventually this algorithm will generate correct output. I just don't want to write the complete explanation of why it works :P. Its a famous ques. called "Wiggle Sort". Google it.