i came across a question....cud anyone suggest how to go with this problem...to me it seems to be based on greedy algo
You are now incharge of a private hall. People book your hall for different purposes like marriage, meetings and other ceremonies we will consider all these events just as a “booking”. You are a very famous person and so is your hall for various facilities. All people want to perform their ceremonies in this hall so they book your hall beforehand. Now you have a problem ,there are many request applications for booking . Each application mentions the start date and no. of days for which it wants to do the booking along with the cost per day you will be pad for that booking. Since you are businessman you have to allot the hall in such a way that you gain maximum profit(maximum amount) out of this. Things you need to keep in mind to make things simpler is : =>You need not to mention the month or year , you can assume the dates are of same month . =>Once you allot the hall to someone you can’t allot it to anyone else till the ceremony is not over. =>Month is only of 30 days. Any start date between 1 and 30(inclusive) is valid. => Booking is done for full day . If your event(to which you allot the hall) ends on suppose 12th of the month you cannot give hall to anyone on 12th you can give on 13th For Ex: two persons request for a booking: BookingReq 1 : StartDate : 12 No. of Days : 3 Amount Perday: 1000 Booking Req2: StartDate : 14 No .of Days 1: Amount Perday : 2000 Then if you allot this hall to First Person.. it is occupied for next 3 days and you can’t give it to second person. “Your Task is to output the BookingReq no. to which you can allot hall to gain maximum profit(maximum amount)”. Input Specification: First Line of input consist of number of test cases M. FirstLine of each test case consist of no. of booking requests N . Followed by N lines.Where Each line contains 3 integers StartDate ,No. of days booking is required and Amount per day , each integer separated by a space. New test case start on a new Line. 1<= Startdate <=30 Ouput Specification Output contains M lines . Each line gives the maximum amount of money you can get by allotting the hall. Sample Input: 1 // no. of test cases 3 //3 booking requests for test case 1 3 4 1200 2 7 900 13 2 200 Ouput: 8900 Regards, PAYAL GUPTA -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
