Skip to main content

1235. Maximum Profit in Job Scheduling

Hi everyone, Today's post is little bit intriguing to me as it took me some time to get t the solution. I have been out of practice for a bit so I was not able to do it in the DP. I didn't want to copy the code. Though i understood the code after i checked its solution in the discussions. Anyways, i tried to do it with heap and with some thinking I was able to do it and with my surprise It performed real well.

I would like to jump to the solution but first I would like to explain a little bit about heaps so you can get better understanding of the code.

A heap is like a special type of list where the smallest (or largest) item is always at the front. Think of it like a priority line at a theme park, where the person with the highest priority goes to the front.

There are two types of heaps:

  1. Min Heap:

    • The smallest item is at the front.
    • It's like standing in a line where the shortest person is always at the front.
  2. Max Heap:

    • The largest item is at the front.
    • It's like standing in a line where the tallest person is always at the front.

In Python, we use the heapq module to work with heaps. Here's a simple example

import heapq

# Create an empty heap
heap = []

# Add some numbers to the heap
heapq.heappush(heap, 4)
heapq.heappush(heap, 1)
heapq.heappush(heap, 7)
heapq.heappush(heap, 3)

# The smallest number is always at the front
smallest = heapq.heappop(heap)

print(smallest) # Output: 1
#Till the second last night where heappop is not done this will be the structure of 
heap

1
/ \
4 7
/
3


#After heapop smallest element will be removed from the heap so it will become

3
/ \
4 7

In this example, heapq.heappush() adds numbers to the heap, and heapq.heappop() takes out the smallest number. It's like letting the person with the highest priority go first in the theme park line.

Heaps are handy because they make it really quick to find and remove the smallest (or largest) item, which is useful in certain types of problems. Just remember, the "priority" is determined by whether it's a min heap (shortest person first) or a max heap (tallest person first).

I will make an entire section for heaps later but for now just know that in heap time complexity of heapify (maintaining heap property), push and pop in O(logN). Finding maximum/minimum takes O(1) time and building a heap has O(N) time complexity.

Now moving on to the solution.

class Solution:
def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
n = len(startTime)
jobs = [[startTime[i], endTime[i], profit[i]] for i in range(n)]
jobs.sort(key=lambda x:x[0])
heap = []
curr_profit, mx_profit = 0, 0

for start, end, profit in jobs:
while heap and heap[0][0]<=start:
end_time, temp = heapq.heappop(heap)
curr_profit = max(curr_profit, temp)
heapq.heappush(heap,(end, curr_profit+profit))
mx_profit = max(mx_profit, curr_profit+profit)
# print(heap)
 
return mx_profit

 in the above code:

        n = len(startTime)
        jobs = [[startTime[i], endTime[i], profit[i]] for i in range(n)] 

  •  We first calculate the number of jobs (n) based on the length of the startTime list. Then, it creates a list of jobs (jobs) by combining the corresponding elements of startTime, endTime, and profit using a list comprehension

    jobs.sort(key=lambda x: x[0])

  • The jobs list is sorted based on the start times of the jobs. This sorting is essential for the subsequent steps, as it allows the algorithm to process the jobs in chronological order.

    heap = []
    curr_profit, mx_profit = 0, 0

  • Here, an empty heap (heap) is initialized, and two variables curr_profit and mx_profit are set to 0. curr_profit is used to keep track of the current profit during the iteration, and mx_profit stores the maximum profit obtained so far.

            for start, end, profit in jobs:
                while heap and heap[0][0] <= start:
                    end_time, temp = heapq.heappop(heap)
                    curr_profit = max(curr_profit, temp)
                heapq.heappush(heap, (end, curr_profit + profit))
                mx_profit = max(mx_profit, curr_profit + profit)
     

    This is where the entire magic happens.

    The main loop iterates through the sorted jobs list. For each job, it checks the heap to find jobs that have already finished (end time is less than or equal to the current job's start time). It pops such jobs from the heap and updates the curr_profit variable accordingly.

    Then, it pushes the current job onto the heap, considering the updated profit. The mx_profit variable is updated to keep track of the maximum profit obtained so far.

     

    In the end we return the mx_profit, giving us the correct answer.

    Performance of the code:

     

    Time complexity - O(nlogn)

    The dominant factor in the time complexity is the sorting of the jobs list, which takes O(n log n) time, where 'n' is the number of jobs. The loop that follows processes each job once, and for each job, it may involve operations like pushing and popping from the heap (logarithmic time in the size of the heap). Therefore, the overall time complexity is O(n log n).

    Space Complexity - O(N)

    We have to create `jobs` and `heap` array and heap structure so it takes N space to store the info about each job.

     

    I hope you like this. If you need any other code solution to be explained do let me know in the comments. Happy coding :)

 

Comments

Post a Comment

Popular posts from this blog

1456, Maximum Number of Vowels in a Substring of Given Length

Hi, folks today I am here with an interesting coding problem from Leetcode. *To directly go to the question please click here. So I will walk through the solution. It will be a brute force and an optimized way solution. I will be explaining the optimized way solutions in depth. # Intuition For any substring of length k, we need to find how many vowels are there in it and provide the highest count of all counts of vowels in a substring. Test Case 1 Input k = 2 and s='asjdee' Output - 2 Explanation: As for substring of length k=2, in the string 's' we have 'ee' when the length is k and the vowels count is 2 Test Case 2 Input k=3 and s='aasdiisdwe' Output - 2 Explanation - For all the substrings with length k = 3 we have 'aas' and 'dii' with 2 vowels each in it. Brute Force - Looping (twice) - Gives TLE (Not recommended) # Approach Create a hashmap (dictionary) with all the vowels in it. Loop through the string till len(s)-k element of strin

1287. Element Appearing More Than 25% In Sorted Array

Hi, Today i bring you new Leetcode problem. Its an easy one :) The problem is - Element Appearing More Than 25% In Sorted Array As qs. explains itself we need to find a number that appears 25% times or more than the length of he array. So for example if array has length of 8 then the resultant number should appear 2 or more times. The constraints given are - 1 <= arr.length <= 100, 0 <= arr[i] <= 10 5 So, lets look at the cases which we may encounter. 1. if length is 1. then the number itself is the result. 2. if length is divisibe by 4 3. if length is not divisible by 4. Let's look at the code now...  class Solution : def findSpecialInteger ( self , arr : List[ int ]) -> int : n = len (arr) start = 0 end = n hm = defaultdict() for i in arr: hm[i] = hm.get(i, 0 )+ 1 for i in hm: if hm[i]>n// 4 : return i Now we will go through the code. Step 1: Initializatio