Last active
May 23, 2017 17:16
-
-
Save tmessinis/8c5772f8dc77dd9fe0725dec32b103d7 to your computer and use it in GitHub Desktop.
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
| """ | |
| You have N pairs of intervals, say integers. | |
| You're required to indentify all intervals that overlap with each other. | |
| For example, if you have | |
| {1, 3} {12, 14} {2, 4} {13, 15} {5, 10} | |
| The answer is {1, 3}, {12, 14}, {2, 4}, {13, 15}. | |
| Note that you don't need to group them, so the result can be in any order like in the example. | |
| Original problem found here: https://goo.gl/sQnNxz | |
| """ | |
| tup_list = [(7, 11), (1, 3), (12, 14), (2, 4), (13, 15), (5, 10), (99, 1000)] | |
| # Brute force | |
| def find_overlap(tup_list): | |
| return_set = set({}) | |
| for tup in tup_list: | |
| for tup_2 in tup_list: | |
| if tup == tup_2: | |
| continue | |
| else: | |
| if tup[1] > tup_2[0] and tup[1] < tup_2[1]: | |
| return_set.add(tup) | |
| return_set.add(tup_2) | |
| return return_set | |
| result = find_overlap(tup_list) | |
| print(result) | |
| print(len(result)) | |
| # O(n) solution..? | |
| def find_overlap_2(tup_list): | |
| return_set = set({}) | |
| idx = 0 | |
| offset = 0 | |
| while idx < len(tup_list): | |
| if idx + offset >= len(tup_list): | |
| idx += 1 | |
| offset = 0 | |
| continue | |
| current_item = tup_list[idx] | |
| offset_item = tup_list[idx + offset] | |
| if (current_item[1] > offset_item[0] and current_item[1] < offset_item[1]) or \ | |
| (current_item[0] < offset_item[1] and current_item[0] > offset_item[0]): | |
| return_set.add(current_item) | |
| return_set.add(offset_item) | |
| offset += 1 | |
| return return_set | |
| result = find_overlap_2(tup_list) | |
| print(result) | |
| print(len(result)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment