Step 1.
Look for the highest deadline - O(n)
Step 2.
Make an subset array to hold the completed jobs of size equal to max deadline & initialize it to 0. - O(n)
Step 3.
Sort the jobs in decreasing order of profit - theta(nlogn)
Step 4.
Place the job in required deadline. If a deadline is occupied, look for all previous deadlines untill an empty slot is found.- O(n^2)
Total time complexity O(n^2) [AC & WC]
For best case, when every job has diff. deadline TC will be theta(nlogn).