Hello

I have my program mostly working (it outputs the correct results) but we aren't allowed to Pythons built in sort.

how would i replace this with a merge, insertion, or bubble sort and still make it work?

my code and requirements are attached

It's a variation of the "first to finish" activity scheduling greedy algorithim that instead goes by "last to start"

example input is a text file. will attach it below code

code

def activitySelection(array): # Sort the list by the finishing time array.sort(key = lambda x: x[2]) # Capture length of list n = len(array) # Storage array for selected activities storage = [] print("The following activities are selected") # Start with the last activity i = n - 1 # Append the last activity by default since that's what we start with in array last-to-start algorithm storage.append(array[i][0]) # Loop through the list in reverse order for idx, j in reversed(list(enumerate(array))): # Compare current activity's finish time to previous activity's start time. # If it's less than the start time than we push the activity number (j[0]) to the storage array. if j[2] <= array[i][1]: storage.append(j[0]) # Set i to the enumerator (idx) i = idx # Return the storage array but reverse it first (to match the sample output solution) return list(reversed(storage)) with open('act.txt') as inFile: next(inFile) storage = [] set = 1 for line in inFile: # Clear trailing white spaces and characters line = line.rstrip() # Check if we've reached array line where there's no leading white space and the length of the storage array is greater than 0 # This tells us that we've reached array new Set of data and should evaluate the current data set we collected. # The else condition will handle storage of the data into array list that's stored into the storage array. if ' ' not in line and len(storage) > 0: print("Set: " + str(set)) # We need to test the first result of the array for data pollution. # The first loop will always append the # of activities, so we need to pass in an array that skips over the bad data if(len(storage[0]) > 1): result = activitySelection(storage[0:]) else: result = activitySelection(storage[1:]) print("Number of activities selected = " + str(len(result))) print("Activities: " + str(result) + ' ') set += 1 storage = [] else: storage.append([int(i) for i in line.split()]) # A final pass that evaluates the rest of the data from the storage array. if len(storage) > 0: print("Set: " + str(set)) result = activitySelection(storage) print("Number of activities selected = " + str(len(result))) print("Activities: " + str(result)) 

TEXT FILE TO TEST WITH

6

11

1 1 4

2 3 5

3 0 6

4 5 7

5 3 9

6 5 9

7 6 10

8 8 11

9 8 12

10 2 14

11 12 16

3

3 6 8

1 7 9

2 1 2

6

1 1 5

2 3 6

3 6 10

4 8 11

5 11 15

6 12 15

11

1 1 4

2 3 5

3 0 6

4 5 7

5 3 9

6 5 9

7 6 10

8 8 11

9 8 12

10 2 14

11 12 16

3

3 6 8

1 7 9

2 1 2

6

1 1 5

2 3 6

3 6 10

4 8 11

5 11 15

6 12 15

Should output:

Set: 1

Number of activities selected = 4

Activities: [2, 4, 9, 11]

Set: 2

Number of activities selected = 2

Activities: [2, 1]

Set: 3

Number of activities selected = 3

Activities: [2, 4, 6]

Set: 4

Number of activities selected = 4

Activities: [2, 4, 9, 11]

Set: 5

Number of activities selected = 2

Activities: [2, 1]

Set: 6

Number of activities selected = 3

Activities: [2, 4, 6]