Skip to content

Instantly share code, notes, and snippets.

@gcallah
Created October 19, 2017 20:08
Show Gist options
  • Save gcallah/bb22ea72d8b15fa965d2f50e6798ae50 to your computer and use it in GitHub Desktop.
Save gcallah/bb22ea72d8b15fa965d2f50e6798ae50 to your computer and use it in GitHub Desktop.
Greedy algorithm Python code.
#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
This file contains Python implementations of greedy algorithms
from Intro to Algorithms (Cormen et al.).
The aim here is not efficient Python implementations
but to duplicate the pseudo-code in the book as closely as possible.
Also, since the goal is to help students to see how the algorithm
works, there are print statements placed at key points in the code.
The performance of each function is stated in the docstring, and
loop invariants are expressed as assert statements when they
are not too complex.
This file contains:
recursive_activity_selector()
greedy_activity_selector()
"""
smalls = [1]
smallf = [0, 4]
start = [0, 1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12]
finish = [0, 4, 5, 6, 7, 9, 9, 10, 11, 12, 14, 16]
def recursive_activity_selector(s, f, k, n):
"""
Args:
s: a list of start times
f: a list of finish times
k: current position in
n: total possible activities
Returns:
A maximal set of activities that can be scheduled.
(We use a list to hold the set.)
"""
m = k + 1
while m < n and s[m] < f[k]: # find an activity starting after our last
# finish
m = m + 1
if m < n:
print("Adding activity " + str(m) + " that finishes at "
+ str(f[m]))
return [m] + recursive_activity_selector(s, f, m, n)
else:
return []
def greedy_activity_selector(s, f):
"""
Args:
s: a list of start times
f: a list of finish times
Returns:
A maximal set of activities that can be scheduled.
(We use a list to hold the set.)
"""
assert(len(s) == len(f)) # each start time must match a finish time
n = len(s) # could be len f as well!
a = []
k = 0
for m in range(1, n):
if s[m] >= f[k]:
a.append(m)
k = m
return a
@o2m2
Copy link

o2m2 commented Jan 2, 2022

how can I run this program plz?

@gcallah
Copy link
Author

gcallah commented Jan 2, 2022

Using Python?

@kaizhelam
Copy link

how to run this program? thank you

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment