Question 1 (Programming Assignment) [40 points] Note This assignment can be solv

Question

Question 1 (Programming Assignment) [40 points]

Note

This assignment can be solved in either Java, Python or C++ (you should pick the language you are most comfortable with). Please make sure to look at the supporting documentation and files for the language of your choosing.

The Problem

The TennisSuperVillian is hell-bent on destroying earth. Humans have one last hope: the great tennis player Serena Williams :

Serena has two choices to neutralize TennisSuperVillian. The first choice is to nuke TennisSuperVillian’s hideout. The second choice is to defeat the TennisSuperVillian in his own game. Serena has to beat TennisSuperVillian in nn special rallies. The ithith rally (0in10in1) needs a given amount of time titi and it has to be finished by time fifi . Each of these rallies are complex and (even) Serena can only play one rally at a time and each rally once it has been started has to be completed without interruption (otherwise TennisSuperVillian wins and the earth gets destroyed). TennisSuperVillian is cunning and has made sure that the only way to defeat him is to finish each rally ii by time fifi . You should also assume that Serena cannot start any of the rallies before time 0. (Also assume that all the titi and fifi are positive integers.)

Serena also has intelligence that TennisSuperVillian has planned an imminent attack soon and she does not have time to try out both choices.

Obviously Serena wants to avoid the first choice because of the collateral damage. However, as mentioned earlier time is short and Serena needs to decide if she can go with the second choice. During her training, she skipped the class on greedy algorithms. Your task is to design an algorithm for Serena that will help her make her decision in timeO(nlog(n))O(nlog(n)).

Input

The first line of the input file will have the number nn, indicating the number of rallies

The next nn lines will have the durations (titi) and deadlines (fifi) for the nn rallies (separated by spaces)

The index of the line under consideration is the ID of that rally. For instance line 0 of the input file (not including the line displaying nn) has the duration (t0t0) and deadline (f0f0) of rally 0

For example:

Output

If you decide that Serena should play out all the rallies, you should output a list of pairs (rally ID, rally start time).

If you decide that the only option Serena has is to nuke TennisSuperVillian's hideout, output an empty list.

For example, using the example input from above:

Note

If your algorithm decides that Serena should play out all the rallies, your output schedule might not match the corresponding output file. That is fine. As long as all the rallies in your schedule finish by their respective deadlines, the grader will give you full points.

Explanation / Answer

Driver.py
------------------------------------------------------------------------
from Solution import *
from readFromFile import *
import sys

def main():

   if (len(sys.argv) < 2):
       print("Please provide the input filepath as the argument")
       sys.exit()

   input_file = sys.argv[1]

   input = readFromFile(input_file)

   #Get answer
   output = HW6_StudentSolution(input)

   print(output)

if __name__ == '__main__':
main()
------------------------------------------------------------------------------
Solution.py
-------------------------------------------------------
from operator import itemgetter
def Solution(rallies):
    final = []
    finaler = []
    myDict = {}
    count = 0
    for x in rallies:
        final.append((count,x[1]))
        myDict[x[1]] = x[0]
        count = count + 1
    final = sorted(final,key=itemgetter(1))
    accum = 0
    count = 0
    for y in final:
            finalTuple = (y[0],accum)
            accum = accum + myDict[y[1]]
            finaler.insert(count, finalTuple)
            if accum > y[1]:
                return []
            count = count + 1
return finaler
----------------------------------------------------------------------------------
readFromFile.py
--------------------------------------------
def readFromFile(inputFile):

   rallies = []

   with open(inputFile, 'r') as file:

       numberOfRallies = int(file.readline())
      
       for i in range(0, numberOfRallies):
           durationAndDeadline = file.readline().split()
           rallies.append((int(durationAndDeadline[0]), int(durationAndDeadline[1])))

return rallies

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.