✅Easy - Detailed Explanation ,Beats - 84.40% 🔥🔥
Intuition\n - main Idea here is, to solve this problem we want jobs with highest profit in contrained difficulty.\n- so we have to compare workers difficulty le
# Intuition\n - main Idea here is, to solve this problem we want jobs with highest profit in contrained difficulty.\n- so we have to compare workers difficulty level to n jobs difficulty level and while doing that we need to check profits also.\n- we can do this linearly for each worker to each job ..but that would be having very exponential time complexity\n- upcourse we can do this in less time and space complexity. lets see how.\n\n\n# Approach\n- we will be creating a pair class here , so we can map each jobs difficulty level to its profit. and we gonna make all pairs\n- now we have to sort that pair array so we will be having increasing difficulty levels . it will help while solving problem\n- we need to sort worker array also, so we can compair the values easily\n- now in our main algorithm, for each worker we will look for which job he can do,and if we find any, we will save the profit for that job in "prev" and will go and check if we get another job which has max profit. and at the end that worker will be having max profit job\n- so idea behind maintaining "prev" variable here, if any worker (except 0th) cant find job less or equal to his difficulty, he can do previous workers max profitable job.(mentioned in quetion one job can be done multiple times)\n- so you can see the idea behind doing sorting here , we can implement two pointers method here on both the arrays\n\n# Complexity\n- Time complexity:\nO(N)+o(NLogN)+O(NlogN)+O(N) = O(NlogN)\n\n- Space complexity:\nO(N)\n\nIF YOU UNDERSTOOD THE SOLUTION AND APPROCH PLEASE DO CONSIDER UPVOTE , IT HELPS ME TO STAY MOTIVATED AND ADD MORE SOLUTONS . THANK YOU FOR READING.\n\n# Code\n```\n///TC - O(NlogN) SC - O(N)\nclass Solution {\n    class Pair{\n        int diff;\n        int prof;\n        Pair(int diff,int prof){\n            this.diff = diff;\n            this.prof = prof;\n        }\n    }\n    public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {\n    \n    int n = difficulty.length;\n\n    Pair[] combine = new Pair[n];\n\n    for(int i=0;i<n;i++){\n        Pair p = new Pair(difficulty[i],profit[i]);\n        combine[i] = p;\n    }\n \n    Arrays.sort(combine,(a,b)-> Integer.compare(a.diff,b.diff));\n\n    Arrays.sort(worker);\n\n    int i = 0 , j=0,totalP = 0 , prev =0;\n\n    while(i<worker.length){\n\n          while(j<n){\n          int d = combine[j].diff;\n          int p = combine[j].prof;\n  //WE GOT A JOB , SAVE IT AND LOOK FOR BETTER JOB\n          if(d<=worker[i]){\n              prev = Math.max(p,prev);\n          }\n  ///IF JOB DIFFICULTY IS GREATER NO NEED TO GO FURTHER , WILL BREAK\n          if(d>worker[i]){\n              break;\n          }\n          j++;\n          }\n  ///KEEP ON ADDING PROFITS HERE\n          totalP+= prev;\n          i++;\n    }\n\n  ///RETURN \n    return totalP;  \n        \n    }\n}\n```
['Java']