A simple proof why greedy works, with diagram
C++ code:\n\n    int minMovesToSeat(vector<int>& seats, vector<int>& students) {\n        sort(seats.begin(), seats.end());\n        sort(students.begin(), stud
C++ code:\n```\n    int minMovesToSeat(vector<int>& seats, vector<int>& students) {\n        sort(seats.begin(), seats.end());\n        sort(students.begin(), students.end());\n        int total = 0;\n        for (int i = 0; i < seats.size(); ++i) {\n            total += abs(seats[i] - students[i]);\n        }\n        return total;\n    }\n```\n\n## when `n = 2`\nWe can use a simple example to examine why greedy algorithm works.\n\nLet\'s say we have `seats = [a1, a2]` and `students = [b1, b2]`, with `a1 < a2`, `b1 < b2`, and `a1 < b1`. Now three cases will happen:\n\n### case 1: `a2 < b1`\n```\n[a1]|-------|[a2]\n                   [b1]|------|[b2]\n```\nThen `(b1 - a1) + (b2 - a2)` is equal to `(b2 - a1) + (b2 - a1)`. In this case, greedy method is *no worse*.\n\n### case 2: `b1 < a2` and `a2 < b2`\n```\n[a1]|-------|[a2]\n      [b1]|-------|[b2]\n```\nClearly `(b1 - a1) + (b2 - a2) < (b2 -a1) < (b2 - a1) + (a2 - b1)`. Greedy method wins.\n\n### case 3: `b1 < a2` and `b2 < a2`\n```\n[a1]|--------------------|[a2]\n        [b1]|----|[b2]\n```\nIn this case, we can easily see `(b1 - a1) + (a2 - b2) < (a2 - a1) < (b2 - a1) + (a2 - b1)`. Greedy wins.\n\nIn all cases, greedy method is *at least not worse* than the alternative approach.\n\n## when `n > 2`\nWe can use induction to prove the general case.
['Greedy', 'C']