In: Computer Science
please write simple python3 program and also explain the logic of program because i am not understanding and crying so much
Problem Statement
There is a very famous old restaurant in ByteLand city,which can serve only 1 customer at any given time.It has B chairs outside for waiting customers.The restautants manager has a list of people who will be coming in today.The i-th customer will arrive at t[i] (all unique) time and will eat for d[i] unit of time.The restaurant attends to each customer as per the following rules:
1) if there is no customer being served currently,a new customer will be served immediately
2) if one customer is being served and there is at least one empty chair in the waiting area,a new customer will go and occupy one empty chair.
3)if the waiting area is full,a new customer will be rejected and will never be served .
4)Waiting area works like a queue and the first to enter will be served first.
Based on the list,the restaurant manager wants to know:
1.How many customers will be rejected today so that she can plan the food quantity accordingly and also 2 .v by what time will she finish serving the last customer.
Input format:
The first line of the input contains two integers N and B(1<=N,B<=100,000)-- The number of customers and the number of chairs in the waiting area.
Then follow N lines with queries descriptions (in chronological order ). Each description consists of two integers t[i] and d[i] ( 1 <= t[i] , d[i]<= 10^9 ) , where t[i] is the moment of time when the i-th customer appears and d[i] is the time customer needs for eating. it is gauranteed that t[i-1] < t[i] for all i >1
Output Format:
Print one integer corresponding to the number of customers who will be rejected and time when the last customer will be finish her meal.
Sample Input1:
5 1
2 9
4 8
10 9
15 2
19 1
Sample Output1
1 22
Explanation
1st customer comes at moment 2,no one is being served hence she will be served immediately.
2nd customer comes at moment 4 , 1rst one is still being served hence she will go and take chair in waiting area
3rd customer comes at moment 10 1rst one is still being served and no chair is empty in waiting area.Hence she will be rejected.
1st customer finishes at moment 11, 2nd customer will come from waiting area to get served and waiting area becomes empty.
4th customer comes at moment 15,2nd customer is being served hence she will move to waiting area.
2nd customer finishes at moment 19, 4th customer will move from waiting area to get served and waiting area becomes empty.
5th customer comes at moment 19,4th customer is being served hence she will move to waiting area
4th customer finishes at moment 21 , 5th customer will move from waiting area to get served and waiting area becomes empty.
5th customer finishes at moment 22
Sample input2
5 1
2 1
3 6
4 5
6 4
7 2
Sample putput 2:
2 14
ANSWER:
I have provided the properly
commented and indented code so you can easily copy the
code as well as check for correct indentation.
I have provided the output image of the code so you can easily
cross-check for the correct output of the code.
Have a nice and healthy day!!
CODE
# fetching first input line n and seats
inp = input()
# input is form of string, fetching spaced number from string in integer format
# using string method split and using list comprehesion to fetch input in int
n, seats = [int(ele) for ele in inp.split()]
# looping n times to take n line inputs
# storing inputs in arrival and delay time lists
arrival = []
delay = []
for i in range(n):
# similar to above input method, fetching inputs
inp = input()
# arr and del time
arr, dly = [int(ele) for ele in inp.split()]
# adding value to lists
arrival.append(arr)
delay.append(dly)
# Algorithm,
# arrival | delay | isEmpytSeat |In Rest Till | EmptySeats | Removed
# 2 | 9 | True | 11 | 1 | 0
# 4 | 8 | True |11 + 8 = 19 | 0 | 0
# 10 | 9 | False | Removed Imm.| 0 | 1
# At 11 - EmptySeats ++ = 1
# 15 | 2 | True | 19+2 = 21 | 0 | 0
# At 19 - EmptySeats ++ = 1
# 19 | 1 | True | 21+1 = 22 | 0 | 0
# Hence, Removed = 1
# last customer in rest till => 22
# code
# defining and initializing variables
# inRestTill init to first customer arrival
inRestTill = arrival[0]
# list index counter
i = 0
# removed customer counter
removed = 0
# empty seats counter, initialy waiting seats + one serving seats empty
empty = seats
# looping for all elements in arrival and delay
while i < n:
# ith customer delay addition to inRestTill
inRestTill += delay[i]
# looping to check, till inRestTill time how many customers coming
# removing k-empty seats customers
# loop counter, from i+1
j = i+1
while (j<n) and (arrival[j]<inRestTill):
# customer j came to rest when serving i
# if seats are fulled removing customer j from list of arrivals
# and delays
# using pop method of list to do so
if empty == 0:
# removing customer from list
arrival.pop(j)
delay.pop(j)
# incrementing removed counter
removed +=1
# decrementing n(size) value by one
n -= 1
print(j)
else:
# if seats present decrementing seat
empty -= 1
# incrementing j counter
j += 1
# initializing seats to empty again, or checking same for next customer
empty = seats
# incrementing i counter
i += 1
print()
print("Removed Customers:",removed)
print("Last Customer left Rest:",inRestTill)
OUTPUT IMAGE