Q4 10 Suppose you are a cable guy and are sent out for jobs to complete in a single day. Given job j; each has a start time s; and finish time f;. Your goal is to complete the most number of jobs assigned. The only requirement is you are allowed to start a job late by y minutes, (there is no travel time between jobs). Otherwise, there is no allowed overlap. So I can have a job that goes 1pm-1:37pm and start another one that goes from 1:30pm to 2:30pm PART A Create and analyze code for a greedy algorithm that follows the greedy strategy of choosing the job that starts the latest compatible to currently selected jobs. (HINT you can order jobs in order of decreasing start time) Part B Prove that the greedy strategy of choosing the job that starts the latest is possible in an optimal solution. (Greedy choice property)

Q4 10 Suppose you are a cable guy and are sent out for jobs to complete in a single day. Given job j; each has a start time s; and finish time f;. Your goal is to complete the most number of jobs assigned. The only requirement is you are allowed to start a job late by y minutes, (there is no travel time between jobs). Otherwise, there is no allowed overlap. So I can have a job that goes 1pm-1:37pm and start another one that goes from 1:30pm to 2:30pm PART A Create and analyze code for a greedy algorithm that follows the greedy strategy of choosing the job that starts the latest compatible to currently selected jobs. (HINT you can order jobs in order of decreasing start time) Part B Prove that the greedy strategy of choosing the job that starts the latest is possible in an optimal solution. (Greedy choice property)

C++ Programming: From Problem Analysis to Program Design

8th Edition

ISBN:9781337102087

Author:D. S. Malik

Publisher:D. S. Malik

Chapter5: Control Structures Ii (repetition)

Section: Chapter Questions

Problem 20PE: When you borrow money to buy a house, a car, or for some other purpose, you repay the loan by making...

See similar textbooks

Similar questions

A performance venue hosts many concerts a year. Performers perform several times a year for the concerts. Each concert has one or more performers and has a name and a specified seating arrangement. A concert is held in one (and only one) of several concert halls, each of which has a room number and the number of seats. Each concert generates revenues from the sales of tickets. Assume that the price of the ticket is the same for the same concert, but different prices for different concerts.Identify several attributes and a key field for each entity. Represent this situation of concerts and performers with an E-R diagram
Bus Loading Problem. You are in charge of filling busses with passengers at a bus terminal. Each bus has space for ten (10) passengers. Four (4) of those spaces can hold only wheelchair passengers, and the other six (6) can hold only non-wheelchair passengers. Busses and both types of passengers arrive at random. As busses arrive, you are to fill them up with passengers. Once a bus is full (containing 6 non-wheelchair, and 4 wheelchair passengers), it is allowed to leave the terminal, along with its passengers. You are responsible only for loading the passengers on the bus and having the bus depart. You do not need to worry about what happens to the busses or passengers after they leave. Each bus process has available to it the functions ArriveAtTerminal(), OpenDoors(), CloseDoors(), and DepartTerminal(). Each passenger process has available to it the functions ArriveAtTerminal() and GetOnBus(). Executing GetOnBus() loads the passenger on the bus, and the function returns when the…
Subject -CSE
Required: Amitabh had a magical cat. That cat once fell down an empty well. As the walls of the well were not completely vertical, the cat could climb up the well. In one day, the cat can climb 1 unit height and the height of the well is h units. The cat starts at the bottom. Every day, a cat would divide into 2 cats. One of them would climb up 1 unit. The other would wait for help. But while waiting it would fall asleep and roll down 1 unit, unless it is already at the bottom, in which case it just remains there. When a cat would reach the top, it would run home toAmitabh. (Schrodinger doesn't know that some of the cats are in a well and so he can't rescue them). It has been d days since the cat fell into the well. How many cats would come out of the well today? You would notice that the number of cats grows very large with each passing day, so output the answer modulo 10^9+7. d = 0 means that the cat has fallen just now and so there's just one cat at the bottom of the well. So you…
Q4: Getting the GradeMichael is taking n courses this semester, numbered from 1 to n.Each of these courses has a final exam. Unfortunately, these examsare all held on the same day.Michael has d days left to study for the exams. In each of these days,he has exactly h hours of free time he can use to study (note thath might be greater than 24 as Michael lives in a different universe witha different time system).Moreover, for the i-th course Michael is taking,he has a learning rate l[i] indicating the number of marks he getson the exam per hour of studying for that course.Michael studies for his exams in 1 hour blocks; for example,he can't study for an exam for 40 minutes then switch to another one.Note that in Michael's universe, final exam grades aren'tcapped at 100. In fact, there's no upper limit on how high they can go.If Michael takes an exam without studying for it, he'll get a 0 on that exam.In order to qualify for a nice scholarship, Michael needsto get at least m marks on each…
Q2: Ginormous Campus There are n buildings scattered around it, numbered from 0 to n-1. These buildings are so far away from each other that the only way to get from one to another is to take a campus bus. There are m campus bus routes. The i-th one (0 <= i < m) takes you from building u_i to building v_i (but not the other way around). These buses run very frequently. Professor Zingaro is deciding where to hold his CSC108 lectures. He believes a building x is accessible from a building y if you can get from y to x taking at most two buses. For his students’ convenience, he wants to hold his lectures in the most accessible building. Help him out by telling him how many buildings the most accessible building is accessible from. In addition, list all buildings that are the most accessible. Filename Your filename for this question must be q2.py. Input The first line of the input contains two space-separated integers n and m, denoting the number of buildings and bus routes,…
A Rajesh teaches a cooking class. The course is attended by NN students, numbered 11 to NN. The cook must participate in the presence before each class, i.e. call out the names of the students one by one and indicate which students are present. Each student has a first and last name. To save time, Rajesh only wants to call up students' first names. However, if there are multiple students with the same first name, the Rajesh must call out the full names (first and last names) of all those students. For any student who does not share a first name with any other student, the cook can still only call that student's first name. Help the Rajesh decide for each student whether to call that student's full name or just their first name. Note: Please Answer in java language only. Input 1 1 hasan jaddouh Output hasan
PYTHON CODE: In this scenario you are the responsible engineer that optimize Air traffic flow of Ataturk Airport. Each day, number of airplanes take-off and landing varies between 50 and 70 each. However, if weather conditions go rough in Istanbul, it affects (decrease) %60 of landing and %40 of take-off. In Istabul possibility of rough weather events observed as 0.3 (%30). Create daily weather for a month considering rough weather possibility and print on screen. Calculate number of airplanes take-off and landing separately every day for a month. Calculate total take-off and landing for a month. Calculate low-median, high-median, median, mean and stdev of take-off and landing every day for a month. Sample Output: daily weather for a month: [1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1] daily take_off for a month: [61, 62, 61, 66, 54, 58, 40, 41, 54, 56, 52, 64, 51, 61, 53, 57, 54, 65, 39, 56, 70, 57, 62, 32, 59, 33, 35, 58, 39, 58] monthly…
A year in the modern Gregorian Calendar consists of 365 days. In reality, the earth takes longer to rotate around the sun. To account for the difference in time, every 4 years, a leap year takes place. A leap year is when a year has 366 days: An extra day, February 29th. The requirements for a given year to be a leap year are: The year must be divisible by 4 If the year is a century year (1700, 1800, etc.), the year must be evenly divisible by 400 Some example leap years are 1600, 1712, and 2016. Write a program that takes in a year and determines whether that year is a leap year. Ex: If the input is 1712, the output is: 1712 is a leap year. Ex: If the input is 1913, the output is: 1913 is not a leap year. 1 2 3 4 5 6 7 8 9 10 11 Put("{} is a leap year.".format(i_year)) print("{} is not a leap year.".format(i_year)) inputYear = Get next input What would be the code?
Dinah Shore of Shore We Can Building is attempting to determine the cost forbuilding a custom lumber dog house. Each dog house starts at a cost of $1000. Eachhouse has a different possible size in square feet, which the user will enter. The sizein square feet must be in the range of 1200-2000 inclusive. However, since each doghouse is made from found wood, the actual size of the dog house varies depending onthe materials they have on hand. Once the size has been entered, create a randomnumber to determine the actual size the house will be. This size number should be inthe range of 800 to 2200. If the actual size of the dog house is over the squarefootage the user entered, they only get charged $3 per square foot. If the actual sizeis equal to or under the square footage entered they get charged $4 per squarefoot. The program should calculate the total cost for the dog house. The output forthis program must include the customer’s name, entered size, actual size and totalcost, in that…
Interest on a credit card’s unpaid balance is calculated using the average daily balance. Suppose that netBalance is the balance shown in the bill, payment is the payment made, d1 is the number of days in the billing cycle, and d2 is the number of days payment is made before billing cycle. Then, the average daily balance is: averageDailyBalance =netBalance x d1-payment x d2d1 If the interest rate per month is, say, 0.0152, then the interest on the unpaid balance is: Interest= averageDailyBalance * 0.0152 Write a program using c++ compiler that accepts as inputnetBalance, payment, d1,d2, and interest rate per month. The program outputs the interest. Format your output to two decimal places.
Java code