Created
November 18, 2015 21:54
-
-
Save EntilZha/e4fc9e0f2ebb5f5cf053 to your computer and use it in GitHub Desktop.
Max Interval Solution
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
{ | |
"cells": [ | |
{ | |
"cell_type": "code", | |
"execution_count": 1, | |
"metadata": { | |
"collapsed": true | |
}, | |
"outputs": [], | |
"source": [ | |
"from collections import namedtuple" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 3, | |
"metadata": { | |
"collapsed": false | |
}, | |
"outputs": [], | |
"source": [ | |
"Interval = namedtuple('Interval', 'start end')\n", | |
"intervals = [Interval(10, 14), Interval(4, 18), Interval(19, 20), Interval(19, 20), Interval(13, 20)]" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 22, | |
"metadata": { | |
"collapsed": false | |
}, | |
"outputs": [], | |
"source": [ | |
"def merge_intervals(intervals):\n", | |
" output = []\n", | |
" n = len(intervals)\n", | |
" if n == 0:\n", | |
" return output\n", | |
" sorted_intervals = sorted(intervals)\n", | |
" output.append(sorted_intervals[0])\n", | |
" for i in range(1, n):\n", | |
" top = output[-1]\n", | |
" if top.end < sorted_intervals[i].end:\n", | |
" output.append(sorted_intervals[i])\n", | |
" elif top.end < sorted_intervals[i].end:\n", | |
" new_int = Interval(top.start, sorted_intervals[i].end)\n", | |
" output.pop()\n", | |
" output.append(new_int)\n", | |
" return max([(i.end - i.start, i) for i in output])" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 23, | |
"metadata": { | |
"collapsed": false | |
}, | |
"outputs": [ | |
{ | |
"data": { | |
"text/plain": [ | |
"(14, Interval(start=4, end=18))" | |
] | |
}, | |
"execution_count": 23, | |
"metadata": {}, | |
"output_type": "execute_result" | |
} | |
], | |
"source": [ | |
"merge_intervals(intervals)" | |
] | |
} | |
], | |
"metadata": { | |
"kernelspec": { | |
"display_name": "Python 3", | |
"language": "python", | |
"name": "python3" | |
}, | |
"language_info": { | |
"codemirror_mode": { | |
"name": "ipython", | |
"version": 3 | |
}, | |
"file_extension": ".py", | |
"mimetype": "text/x-python", | |
"name": "python", | |
"nbconvert_exporter": "python", | |
"pygments_lexer": "ipython3", | |
"version": "3.5.0" | |
} | |
}, | |
"nbformat": 4, | |
"nbformat_minor": 0 | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Credit to here for main algorithm: http://www.geeksforgeeks.org/merging-intervals/