Greedy(Figure proof)sort/counting sort| 1-liner ||0ms beats 100%
Intuition\n Describe your first thoughts on how to solve this problem. \nGreedy needs a proof; a proof for n=2 is given: "keep order$\leq$ crossing"\nThe implem
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nGreedy needs a proof; a proof for n=2 is given: "keep order$\\leq$ crossing"\nThe implementation is easy, using sort or counting sort\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Use system built-in sort to sort both arrays \n2. Use counting sort to sort both arrays\n3. Compute the `sum(abs(stududents[i]-seats [i]) for i )`\n# Math proof\n\nConsider $ n = 2 $. Let $ s_0 < s_1 $ denote students and $ t_0 < t_1 $ denote  seats. We need to show that the minimum distance is \n$$\nd = |s_0 - t_0| + |s_1 - t_1|\\leq  |s_0-t_1|+|s_1-t_0|\n$$\nkeep order$\\leq$ crossing. \nFor better understanding, it can be reduced to 3 cases like in the figure to consider the lengths for line segments.\n![Line_seg.png](https://assets.leetcode.com/users/images/c5f3f902-b4b7-4584-bd79-03f630a819ad_1718271761.151478.png)\nFor simplicity, may assume $s_0 <t_0$ (otherwise swap these 2 line segments). these 3 cases are shown in figure.\ncase 1: $(s_0, s_1), (t_0, t_1)$ <ins>2 open  segments has no intersection</ins>. In tis case, $d = |s_0 - t_0| + |s_1 - t_1|=  |s_0-t_1|+|s_1-t_0|.$\ncase 2: $s_0<t_0<s_1<t_1$ <ins>2 segments has an intersection but not a whole segment</ins>, say $(t_0, s_1)$: In this case, along$|s_0-t_1|\\geq |s_0 - t_0| + |s_1 - t_1|$ \nso $|s_0 - t_0| + |s_1 - t_1|\\leq  |s_0-t_1|+|s_1-t_0|$.\ncase 3  $s_0<t_0<t_1<s_1$ <ins>one segment is a subset of the other</ins> :$|s_0 - t_0|+|t_0-t_1| + |s_1 - t_1|=|s_0-s_1|\\implies  d \\leq  |s_0-t_1|+|s_1-t_0|$.\nFor general $n$, one needs the induction to prove which is formal.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n\\log n) \\to O(n+M)$$ where $M=\\max(|seats|, |students|)$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$O(sort)$\n# Code using sort||C++ 0ms Python 1-line\n```Python []\nclass Solution:\n    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n        return sum(abs(x-y) for x, y in zip(sorted(seats), sorted(students)))\n        \n```\n```C++ []\nclass Solution {\npublic:\n    int minMovesToSeat(vector<int>& seats, vector<int>& students) {\n        const int n=seats.size();\n        sort(seats.begin(), seats.end());\n        sort(students.begin(), students.end());\n        int moves=0;\n        for (int i=0; i<n; i++) \n            moves+=abs(students[i]-seats[i]);\n        return moves;\n    }\n};\n\n\n\n\n\nauto init = []() {\n    ios::sync_with_stdio(false);\n    cin.tie(nullptr);\n    cout.tie(nullptr);\n    return \'c\';\n}();\n```\n# C++ using counting sort |||0ms beats 100%\n```\nclass Solution {\npublic:\n    inline void  counting_sort(vector<int>& arr){\n        int freq[101]={0};\n        for(int x: arr) freq[x]++;\n        int cnt=0;\n        for(int x=1; x<=100; x++){\n            int f=freq[x];\n            if (f==0) continue;\n            fill(arr.begin()+cnt, arr.begin()+cnt+f, x);\n            cnt+=f;\n        }\n\n    }\n    int minMovesToSeat(vector<int>& seats, vector<int>& students) {\n        const int n=seats.size();\n        counting_sort(seats);\n        counting_sort(students);\n        int moves=0;\n        for (int i=0; i<n; i++) \n            moves+=abs(students[i]-seats[i]);\n        return moves;\n    }\n};\n\n\n\n\n\nauto init = []() {\n    ios::sync_with_stdio(false);\n    cin.tie(nullptr);\n    cout.tie(nullptr);\n    return \'c\';\n}();\n```
['Math', 'Greedy', 'Sorting', 'Counting Sort', 'C++', 'Python3']