Easiest Greedy Solution II Explained Line-by-Line (C++, Java, Python)
Intuition\n Describe your first thoughts on how to solve this problem. \n# Topic : Greedy\nGreedy algorithms are a class of algorithms that make locally optimal
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n# Topic : Greedy\nGreedy algorithms are a class of algorithms that make locally optimal choices at each step with the hope of finding a global optimum solution. In these algorithms, decisions are made based on the information available at the current moment without considering the consequences of these decisions in the future. The key idea is to select the best possible choice at each step, leading to a solution that may not always be the most optimal but is often good enough for many problems. (GFG Reference)\n\n\nA thorough proof is essential to demonstrate the correctness of a perfect Greedy solution.\n\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n* Greedy Solution\n\n   The objective is to minimize the total travel distance required for students to reach their assigned seats.\n\n   The idea involves assigning students starting from the smallest position to seats in ascending order, ensuring that each student is placed in the closest available seat, beginning with the smallest seat position.\n\n   We can simplify the process by sorting both the seats and students arrays. Then the total distance is the sum of abs(seats[i] - students[i]) for 0 <= i < studeents.length.\n* Proof:\n\n````\n* Student A\'s position : ai\n* Student B\'s position : aj\n* First seat position : bi\n* Second seat position : bj\n\nai <= aj and bi <= bj\n\nlet d1 = |ai - bi| + |aj - bj| (original total travel distance)\nlet d2 = |ai - bj| + |aj - bi| (cross assignment total travel distance)\n\nCase1 : bi <= bj <= ai <= aj\n\t\t\td1 = ai - bi + aj - bj\n\t\t\td2 = ai - bj + aj - bi = d1  \n\t\t\tConclusion : d1 = d2\n\nCase2 : bi <= ai <= bj <= aj\n\t\t\td1 = ai - bi + aj - bj = (aj - bi) - (bj - ai)\n\t\t\td2 = bj - ai + aj - bi  = (aj - bi) + (bj - ai)\n\t\t\tConclusion :  (bj - ai) >= 0, d1 >= d2\n\t\t\t\nCase3 : bi <= ai <= aj <= bj\n\t\t\td1 = ai - bi + bj - aj = (bj - bi) - (aj - ai)\n\t\t\td2 = bj - ai + aj - bi  = (bj - bi) + (aj - ai)\n\t\t\tConclusion :  (aj - ai) >= 0, d1 >= d2\n\t\t\t\nCase4 : ai <= bi <= bj <= aj\n\t\t\td1 = bi - ai + aj - bj = (aj - ai) - (bj - bi)\n\t\t\td2 = bj - ai + aj - bi  = (aj - ai) + (bj - bi)\n\t\t\tConclusion :  (bj - bi) >= 0, d1 >= d2\n\t\t\t\nCase5 : ai <= bi <= aj <= bj\n\t\t\td1 = bi - ai + bj - aj = (bj - ai) - (aj - bi)\n\t\t\td2 = bj - ai + aj - bi  = (bj - ai) + (aj - bi)\n\t\t\tConclusion :  (aj - bi) >= 0, d1 >= d2\n\t\t\t\nCase6 : ai <= aj <= bi <= bj\n\t\t\td1 = bi - ai + bj - aj = (bj - aj) - (bi - ai)\n\t\t\td2 = bj - ai + bi - aj  = (bj - aj) + (bi - ai)\n\t\t\tConclusion :  d1 = d2\n````\n\n# Complexity\n- Time complexity:\n-     O(n log n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n-     O(1)\n```C++ []\nclass Solution {\npublic:\n    int minMovesToSeat(vector<int>& seats, vector<int>& students) {\n        int ans = 0;\n        sort(seats.begin(), seats.end());\n        sort(students.begin(), students.end());\n        for(int i = 0; i < seats.size(); i++) {\n            ans += abs(seats[i] - students[i]);\n        }\n        return ans;\n    }\n};\n```\n```python []\nclass Solution:\n    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n        c=0\n        seats.sort()\n        students.sort()\n        for i in range(len(students)):\n            c+=abs(students[i]-seats[i])\n        return c\n```\n```java []\nclass Solution {\n    public int minMovesToSeat(int[] seats, int[] students) {\n        int ans = 0;\n        Arrays.sort(seats);\n        Arrays.sort(students);\n        for (int i = 0; i < seats.length; i++) {\n            ans += Math.abs(seats[i] - students[i]);\n        }\n        return ans;\n    }\n}\n```\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n
['Python3']