diff options
Diffstat (limited to 'AlgoDesignAndTechniqueEdxPython/sources/covering_segment.py')
-rw-r--r-- | AlgoDesignAndTechniqueEdxPython/sources/covering_segment.py | 33 |
1 files changed, 33 insertions, 0 deletions
diff --git a/AlgoDesignAndTechniqueEdxPython/sources/covering_segment.py b/AlgoDesignAndTechniqueEdxPython/sources/covering_segment.py new file mode 100644 index 0000000..1093565 --- /dev/null +++ b/AlgoDesignAndTechniqueEdxPython/sources/covering_segment.py @@ -0,0 +1,33 @@ +# Uses python3 +import sys +from collections import namedtuple + +Segment = namedtuple('Segment', 'start end') + + +def getSortedListOfSegs(segList): + segList.sort() + return segList + + +def getOptimalPoints(segList): + if len(segList) == 1: + return [segList[0].start] + if segList[0].end <= segList[1].start: + result = [segList[0].end] + if segList[1].start == segList[1].end: + if len(segList) == 2: + return result + else: + result.extend(getOptimalPoints(segList[2:])) + return result + else: + if segList[0].end >= segList[1].end: + result = [segList[1].end] + del(segList[1]) + result.extend(getOptimalPoints(segList[1:])) + return result + else: + result = [segList[0].end] + result.extend(getOptimalPoints(segList[1:])) + return result
\ No newline at end of file |