diff options
Diffstat (limited to 'AlgoDesignAndTechniqueEdxPython/sources/covering_segment.py')
-rw-r--r-- | AlgoDesignAndTechniqueEdxPython/sources/covering_segment.py | 110 |
1 files changed, 86 insertions, 24 deletions
diff --git a/AlgoDesignAndTechniqueEdxPython/sources/covering_segment.py b/AlgoDesignAndTechniqueEdxPython/sources/covering_segment.py index 1093565..b083e31 100644 --- a/AlgoDesignAndTechniqueEdxPython/sources/covering_segment.py +++ b/AlgoDesignAndTechniqueEdxPython/sources/covering_segment.py @@ -5,29 +5,91 @@ from collections import namedtuple Segment = namedtuple('Segment', 'start end') -def getSortedListOfSegs(segList): - segList.sort() - return segList +# 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 +# +# +# def getOptimalPoints1(segList): +# if len(segList) == 1: +# return [segList[0].start] +# if segList[0] == segList[1]: +# return getOptimalPoints1(segList[1:]) +# if segList[0].start == segList[0].end: +# result = [segList[0].end] +# result.extend(getOptimalPoints1(segList[1:])) +# return result +# if segList[0].start == segList[1].start: +# result = [segList[0].end] +# result.extend(getOptimalPoints1(segList[1:])) +# return result +# if segList[0].end < segList[1].start: +# result = [segList[0].end] +# result.extend(getOptimalPoints1(segList[1:])) +# return result +# else: +# if segList[0].end == segList[1].start: +# result = [segList[0].end] +# result.extend(getOptimalPoints1(segList[1:])) +# return result +# else: # segList[0].end > segList[1].start +# if segList[0].end < segList[1].end: +# result = [segList[0].end] +# result.extend(getOptimalPoints1(segList[1:])) +# return result +# if segList[0].end == segList[1].end: +# result = [segList[1].end] +# result.extend(getOptimalPoints1(segList[1:])) +# return result +# else: +# result = [segList[1].end] +# del(segList[1]) +# result.extend(getOptimalPoints1(segList)) +# return result -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 +def getOptimalPoints2(segList): + index = 0 + points = [] + while index < len(segList): + points.append(segList[index].end) + index = index + 1 + while index < len(segList) and segList[index].start <= points[-1]: + if segList[index].end < points[-1]: + points[-1] = segList[index].end + index = index + 1 + return points + +if __name__ == '__main__': + input = sys.stdin.read() + n, *data = map(int, input.split()) + segments = set(map(lambda x: Segment(x[0], x[1]), zip(data[::2], data[1::2]))) + segments = list(segments) + segments.sort() + points = getOptimalPoints2(segments) + print(len(points)) + for p in points: + print(p, end=' ')
\ No newline at end of file |