C# Solution for Most Profit Assigning Work Problem
Intuition\n Describe your first thoughts on how to solve this problem. \nThe main intuition behind the solution is to match each worker with the most profitable
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe main intuition behind the solution is to match each worker with the most profitable job they can handle by using a combination of sorting and a sliding window technique. This approach ensures that each worker is assigned the best possible job based on their ability, thereby maximizing the total profit.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1.\tPair Jobs with Profit and Sort by Difficulty:\n\t\u2022\tCreate a list of pairs where each pair contains the difficulty and profit of a job.\n\t\u2022\tSort this list based on job difficulty. Sorting the jobs helps in efficiently finding the most profitable job that a worker can perform.\n2.\tCreate a Map for Maximum Profit by Difficulty:\n\t\u2022\tIterate through the sorted jobs and maintain a dictionary where the key is the job difficulty and the value is the maximum profit up to that difficulty.\n\t\u2022\tThis map allows quick lookup of the maximum profit for any given difficulty.\n3.\tSort Workers by Ability:\n\t\u2022\tSort the array of workers\u2019 abilities. This sorting ensures that we process each worker in increasing order of their ability, making it easier to use a sliding window to maintain the maximum profit up to the current worker\u2019s ability.\n4.\tCalculate Total Profit:\n\t\u2022\tUse a sliding window technique to maintain the maximum profit for the job difficulties encountered so far.\n\t\u2022\tFor each worker, iterate through the jobs (using a pointer) to find the highest difficulty job they can handle and update the current maximum profit accordingly.\n\t\u2022\tAccumulate this maximum profit for each worker to calculate the total profit.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n1.\tSorting Jobs and Workers:\n\t\u2022\tSorting the jobs by difficulty: O(n log n)\n\t\u2022\tSorting the workers by their ability: O(m log m)\n2.\tCreating the Maximum Profit Map:\n\t\u2022\tIterating through the sorted jobs to create the maximum profit map: O(n)\n3.\tCalculating Total Profit:\n\t\u2022\tIterating through the workers and using a pointer to iterate through the jobs (the sliding window technique): O(m + n)\n\nThe overall time complexity is O(n log n + m log m) because the dominant terms are the sorting operations.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\u2022\tStoring the Jobs: O(n) space for the list of job pairs.\n\u2022\tStoring the Maximum Profit Map: O(n) space for the dictionary of maximum profits.\n\nThe overall space complexity is O(n).\n\n# Code\n```\npublic class Solution {\n    public int MaxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {\n        int n = difficulty.Length;\n        \n        // Step 1: Pair jobs and sort by difficulty\n        List<int[]> jobs = new List<int[]>();\n        for (int i = 0; i < n; i++) {\n            jobs.Add(new int[] { difficulty[i], profit[i] });\n        }\n        jobs.Sort((a, b) => a[0].CompareTo(b[0]));\n        \n        // Step 2: Create max profit map\n        Dictionary<int, int> maxProfitMap = new Dictionary<int, int>();\n        int maxProfit = 0;\n        foreach (var job in jobs) {\n            maxProfit = Math.Max(maxProfit, job[1]);\n            if (!maxProfitMap.ContainsKey(job[0])) {\n                maxProfitMap[job[0]] = maxProfit;\n            } else {\n                maxProfitMap[job[0]] = Math.Max(maxProfitMap[job[0]], maxProfit);\n            }\n        }\n        \n        // Step 3: Sort workers by ability\n        Array.Sort(worker);\n        \n        // Step 4: Calculate total profit\n        int totalProfit = 0;\n        int currentMaxProfit = 0;\n        int jobIndex = 0;\n        \n        foreach (var ability in worker) {\n            // Update currentMaxProfit for the worker\'s ability\n            while (jobIndex < jobs.Count && jobs[jobIndex][0] <= ability) {\n                currentMaxProfit = Math.Max(currentMaxProfit, jobs[jobIndex][1]);\n                jobIndex++;\n            }\n            totalProfit += currentMaxProfit;\n        }\n        \n        return totalProfit;\n    }\n}\n```
['C#']