How about this?
For the sake of simplicity, let's say that people move to the right.
1. Simulate until there's one person in front of a chair (O(n*m) over the number of positions and the number of people).
2. Remove the person and the chair (O(1)).
3. If there are no more chairs (O(1)), terminate.
4. Find the first chair to the left of the one you just removed (O(1)).
5. If this is the last chair, find the first person to its left (O(1)) and remove them and the chair, then terminate.
6. Let's call the position of this chair b, and the position of the first chair to its left, a.
7. The next person to sit at b should be the first one to the left in (a;b]. O(1).
8. If there's no such person, set the chair at a as the current chair and go to step 6.
9. Remove the chair at b and the person.
10. Set the chair at a as the current chair and go to step 6.
Step 1 is the weak link in the algorithm. Suppose you have people at positions 2, 3, and 4, and chairs at positions 1 and 2^641.
I believe there's an O(n) solution over the number of chairs. I'll leave that one up to you.
There's also one edge case where this algorithm as it is performs poorly:
1 2

Chairs: ____*****
People: ****_____

I think there's a simple fix, which I'll also leave to you.