Average Waiting Time - Leetcode 1701 - Python
VloĆŸit
- Äas pĆidĂĄn 23. 07. 2024
- đ neetcode.io/ - A better way to prepare for Coding Interviews
đ§âđŒ LinkedIn: / navdeep-singh-3aaa14161
đŠ Twitter: / neetcode1
â BLIND-75 PLAYLIST: âą Two Sum - Leetcode 1 -...
Problem Link: leetcode.com/problems/average...
0:00 - Read the problem
0:30 - Drawing Explanation
6:08 - Coding Explanation
leetcode 1701
#neetcode #leetcode #python - VÄda a technologie
It was fairly easy problem. Solved it on my own in Linear time which beats 89%.
OMG I came up with exact same logic as your.
Below is my code -
class Solution:
def averageWaitingTime(self, customers: List[List[int]]) -> float:
end = 0
delay = 0
for start, duration in customers:
if end > start:
delay += end - start
else:
end = start
delay += duration
end += duration
return delay/len(customers)
Same here, exact same code even apart from variable namesđ
I feel like a more intuitive way would be to just keep the time running (incrementing the finish times), then subtract the time by which the customer arrives. In any case, if the time is less than the arrival time of the customer, reset the current time to the arrival time of the customer. Then continue with the subtraction.
Minor difference, but can be easier to understand.
int ct=cus[0][0];
double ans=0;
for(int i=0;i
Same solution with good variable names to understand.
def func(customers):
curr_time = 0
total_wait = 0
for arrival, preparation_time in customers:
if arrival > curr_time:
curr_time = arrival
curr_time += preparation_time
total_wait += curr_time-arrival
return total_wait/len(customers)
yeah this is much better to understand. Well done sir
def averageWaitingTime(self, customers):
total, prev = 0, customers[0][0]
for arrival, time in customers:
if prev >= arrival:
prev += time
else:
prev = arrival
prev += time
total += (prev - arrival)
return total / (len(customers))
posted right after i solved it lol
more intuitive approach.
double averageWaitingTime(vector& customers) {
int prevEndTime = 0;
double totalWaitTime = 0.0;
for (const auto& customer : customers) {
int arrival = customer[0];
int time = customer[1];
int startTime = max(arrival, prevEndTime);
int endTime = startTime + time;
int waitTime = endTime - arrival;
totalWaitTime += waitTime;
prevEndTime = endTime;
}
return totalWaitTime / customers.size();
}
Interesting question
now make so that the chef isint restricted to prepare foods in the order of customers to minimise sum of waiting time, or same problem but with a maximium waiting time per customer, am curious what optimisations you can do tgats not bruteforce
Nice.
I think there's also the edge case where customer arrive at same time. Maybe?
But I think it is easy to account for that.
Solved it !! An operating system process scheduling kind of problem !
you're actually really good i underestimated you
@@pastori2672 It's ok. I am not that great though!
Java Solution
class Solution {
public double averageWaitingTime(int[][] customers) {
double sum = 0;
int max = 0;
for (int[] c : customers) {
max = Math.max(max,c[0]);
sum += max - c[0] + c[1];
max = max + c[1];
}
return sum / customers.length;
}
}
These are the kind of problems which solution comes to your mind when you really understand what's happening
That's a lot of problems. Talk it out, draw it, take your sweet time before you start to code
I had the exact same code as you, but when I ran it, leetcode kept rounding my answer down, which made it wrong(in the second test case, the correct answer was 3.25, but leetcode rounded mine down to 3.00). I have tried converting the answer to float but to no avail. Please help me fix it. This seems like a strange problem :(((((
9:00 yeah, I agree with you, I'm not really a fan of the code golf python solutions haha I'd like to understand what's going on at a quick glance.
If else is more readable
This is my solution, I did change the input array, don't know if that allowed but whatever:
totalTime = 0
for i in range(len(customers) - 1):
arrive, time = customers[i]
if arrive + time > customers[i + 1][0]:
customers[i + 1][1] += arrive + time - customers[i + 1][0]
totalTime += time
return (totalTime + customers[-1][1]) / len(customers)
Here's my solution in Java:
class Solution {
public double averageWaitingTime(int[][] customers) {
/*
1. If no previous wait time, start preparing immediately
2. If has a previous wait time (windows overlapping), we slide second overlapping window to the finish of first window.
*/
int start = customers[0][0];
int finish = start + customers[0][1];
int time = (finish) - start;
double sum = time;
for (int i = 1; i < customers.length; i++) {
if (finish > customers[i][0]) {
start = finish;
finish = start + customers[i][1];
time = finish - customers[i][0];
}
else {
start = customers[i][0];
finish = start + customers[i][1];
time = finish - start;
}
sum += time;
}
return (double) sum / customers.length;
chef javascriptđ
For a noob, can someone explain why/how 't' is updated at the end? How can 't' be greater than 'arrival' if it's 0? I get the solution but I don't get how 't' is being updated after we say 'if t > arrival'
Do a dry run for the code. It makes things much more clearer.
@@faaeizkhan6134 I did, but Iâm still wondering the same thing. I guess itâs just how Python works
âââ@@datchkh the first loop of this code won't check the "t > arrival" and t will assign to arrival and the next loop "t > arrival" will be checked
Firstâ€ïž
it took half day to solve....
res = 0
referance = 0
for i in customers:
referance = max(i[0]+i[1], referance+i[1])
res += referance - i[0]
return res / len(customers)
```
def averageWaitingTime(self, customers: List[List[int]]) -> float:
time = 1
average = 0
for [arrives_at, preparation_time] in customers:
if arrives_at > time:
time += abs(time - arrives_at)
time += preparation_time
average += abs(arrives_at - time)
return average / len(customers)
```
All these solution look like copies lol.
Not really a medium i guess