[Greedy + Formal Proof + Tutorial] Minimum Number of Moves to Seat Everyone
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. 
**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**A thorough proof is essential to demonstrate the correctness of a perfect Greedy solution.**\n\n___\n\n## Greedy Solution\nThe objective is to minimize the total travel distance required for students to reach their assigned seats. \n\nThe 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\nWe 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`. <br/><br/>\n\n## Proof \nTo establish the validity of the proposed idea, we will employ a **proof by contradiction** method.\n\nWith the above approach, there are no instances of **cross assignment**. Let\'s use the following to illustrat the deination of **cross assignment**.\n<br/>\nNo  **cross assignment**\n\n![image](https://assets.leetcode.com/users/images/fea2ee7a-c1d2-4f4b-ab71-ee40179151c8_1718239466.8789008.png)\n\nIn the above assignment, each student starts from the smallest position and is assigned to a seat in ascending order based on their position, which is the optimized assignment.\n<br/><br/>\n\nWith  **cross assignment**\n![image](https://assets.leetcode.com/users/images/a88355ad-95fa-46b6-9da1-ab7bdc028c35_1718239633.526677.png)\n\nWe first assume we have only two students **A** and **B**. \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\nThe proof has not finished yet ! With the above formula, we prove that any exchange of two students is unable to result in a smaller travel distance. But what happens with more than 2 students? Let\'s assume A takes B\'s seat, B takes C\'s seat, C takes D\'s seat, and so on. However, there must be a node that takes A\'s seat back finally.\n\nLet\'s suppose **A** represents the initial student holding the` i-th` smallest position who opts not to occupy the seat corresponding to their` i-th` smallest position. We can then define a chain, denoted as `A -> B -> C -> D ... -> A`, as a connected component. \n\nWe begin by sorting the students to their correct match positions. We then start by taking the student with the smallest position and exchange it with the student currently occupying that position. If we only consider these two students, they form a **cross assignment** relationship, and switching them back will result in a better solution.\n\n**In conclusion** : If we sort these students back to match their original seats with no assignments, the result would only improve.\n\n## Code\n<iframe src="https://leetcode.com/playground/4Bov3vmm/shared" frameBorder="0" width="600" height="300"></iframe>\n\n**Complexity**:\n* Time Complexity : `O(n log n)`\n* Space Complexity : `O(1)`\n\n**Feel free to leave a comment if something is confusing, or if you have any suggestions on how I can improve the post.**
['Greedy', 'C', 'PHP', 'Python', 'Java', 'Go', 'JavaScript']