Easy Java Solution | Sorting + Binary Search
Intuition\nThe problem is to assign jobs to workers such that each worker gets the most profitable job they can handle based on their skill level. The key steps
# Intuition\nThe problem is to assign jobs to workers such that each worker gets the most profitable job they can handle based on their skill level. The key steps are:\n\n1. Pair each job\'s difficulty with its profit.\n2. Sort the jobs by difficulty.\n3. For each worker, find the most profitable job they can do using  binary search.\n\n# Approach\n**1. Pairing and Sorting:**\n\n- Create pairs of job difficulties and profits.\n- Sort these pairs based on difficulty.\n\n**2. Preprocessing for Maximum Profit:**\n\n- Ensure that for any given difficulty, we have the maximum possible profit for that difficulty or any easier job. This is done by iterating through the sorted pairs and updating the profit to be the maximum seen so far.\n\n**3. Binary Search for Optimal Job Assignment:**\n\n- For each worker, use binary search to find the hardest job they can do, and add the corresponding profit to the total profit.\n\n# Complexity\n- **Time complexity:**\n    - Sorting the arr array takes O(nlogn), where n is the number of jobs.\n    - Preprocessing the maximum profits takes O(n).\n    - For each worker, the binary search takes O(logn). Since there are m workers, this step takes O(mlogn).\n\nOverall, the time complexity is O(nlogn+mlogn).\n\n- **Space complexity:**\n    - The space complexity is O(n) due to the auxiliary array arr used to store the pairs.\n\n# Code\n```\nclass Pair{\n    int first;\n    int second;\n    public Pair(int first, int second){\n        this.first = first;\n        this.second = second;\n    }\n}\nclass Solution {\n    public int solve(Pair[] arr, int x){\n        int start = 0;\n        int end = arr.length - 1;\n        int max = 0;\n\n        while(start <= end){\n            int mid = start + (end - start)/2;\n            if(arr[mid].first <= x){\n                max = arr[mid].second;\n                start = mid + 1; \n            }\n            else{\n                end = mid - 1;\n            }\n        }\n        return max;\n    }\n    public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {\n        Pair[] arr = new Pair[difficulty.length];\n        for(int i = 0;i<difficulty.length;i++){\n            arr[i] = new Pair(difficulty[i],profit[i]);\n        }\n        Arrays.sort(arr,new Comparator<Pair>(){\n            public int compare(Pair p1, Pair p2){\n                return Integer.compare(p1.first,p2.first);\n            }\n        });\n        for(int i = 1;i<arr.length;i++){\n            arr[i].second = Math.max(arr[i].second,arr[i - 1].second);\n        }\n        int ans = 0;\n        for(int i = 0;i<worker.length;i++){\n            ans += solve(arr,worker[i]);\n        }\n        return ans;\n    }\n}\n```
['Binary Search', 'Sorting', 'Java']