# coding=utf8
# the above tag defines encoding for this document and is for Python 2.x compatibility
import re
regex = r"\#(.*?)\*\*(.*?)\*\*"
test_str = ("Here’s an extended version of the previous explanation, now including **problem definitions**, **approaches**, and **examples** for each interval problem:\n\n"
"---\n\n"
"### 1. **Basic Interval Problems**\n\n"
"#### a) **Finding Overlaps Between Two Intervals**\n\n"
"- **Problem Definition**: Given two intervals, determine if they overlap. Two intervals overlap if they share at least one point in common.\n"
" \n"
"- **Approach**: \n"
" - Check if the start of one interval is before the end of the other and vice versa.\n"
" \n"
"- **Example**: \n"
" - Interval A = [1, 5], Interval B = [4, 9].\n"
" - Output: True (they overlap).\n\n"
"```python\n"
"def do_intervals_overlap(interval1, interval2):\n"
" return interval1[0] <= interval2[1] and interval2[0] <= interval1[1]\n\n"
"# Example\n"
"interval1 = [1, 5]\n"
"interval2 = [4, 9]\n"
"print(do_intervals_overlap(interval1, interval2)) # True\n"
"```\n\n"
"#### b) **Union of Two Intervals**\n\n"
"- **Problem Definition**: Given two intervals, return the union of the intervals if they overlap or are adjacent. If they do not overlap, return both intervals.\n\n"
"- **Approach**: \n"
" - If the intervals overlap, return the minimum start and maximum end of the two intervals.\n\n"
"- **Example**: \n"
" - Interval A = [1, 5], Interval B = [4, 9].\n"
" - Output: [1, 9].\n\n"
"```python\n"
"def union_intervals(interval1, interval2):\n"
" if do_intervals_overlap(interval1, interval2):\n"
" return [min(interval1[0], interval2[0]), max(interval1[1], interval2[1])]\n"
" return [interval1, interval2]\n\n"
"# Example\n"
"print(union_intervals([1, 5], [4, 9])) # [1, 9]\n"
"```\n\n"
"#### c) **Intersection of Two Intervals**\n\n"
"- **Problem Definition**: Find the intersection of two intervals. The intersection is the range that is covered by both intervals.\n\n"
"- **Approach**: \n"
" - If the intervals overlap, the intersection is the maximum of the start points and the minimum of the end points.\n\n"
"- **Example**: \n"
" - Interval A = [1, 5], Interval B = [3, 9].\n"
" - Output: [3, 5].\n\n"
"```python\n"
"def intersection_intervals(interval1, interval2):\n"
" if do_intervals_overlap(interval1, interval2):\n"
" return [max(interval1[0], interval2[0]), min(interval1[1], interval2[1])]\n"
" return None\n\n"
"# Example\n"
"print(intersection_intervals([1, 5], [3, 9])) # [3, 5]\n"
"```\n\n"
"---\n\n"
"### 2. **Multiple Intervals Problems**\n\n"
"#### a) **Merging Overlapping Intervals**\n\n"
"- **Problem Definition**: Given a set of intervals, merge all the overlapping ones.\n\n"
"- **Approach**: \n"
" - Sort the intervals by their start time, then iterate through them and merge overlapping intervals.\n\n"
"- **Example**: \n"
" - Intervals = [[1, 5], [2, 6], [8, 10]].\n"
" - Output: [[1, 6], [8, 10]].\n\n"
"```python\n"
"def merge_intervals(intervals):\n"
" intervals.sort(key=lambda x: x[0])\n"
" merged = [intervals[0]]\n"
" \n"
" for i in range(1, len(intervals)):\n"
" if merged[-1][1] >= intervals[i][0]:\n"
" merged[-1][1] = max(merged[-1][1], intervals[i][1])\n"
" else:\n"
" merged.append(intervals[i])\n"
" \n"
" return merged\n\n"
"# Example\n"
"print(merge_intervals([[1, 5], [2, 6], [8, 10]])) # [[1, 6], [8, 10]]\n"
"```\n\n"
"#### b) **Finding Gaps Between Intervals**\n\n"
"- **Problem Definition**: Given a set of intervals, find the gaps where no interval exists.\n\n"
"- **Approach**: \n"
" - Sort intervals by start time. Identify gaps by checking the end of one interval and the start of the next.\n\n"
"- **Example**: \n"
" - Intervals = [[1, 5], [7, 10]].\n"
" - Output: [5, 7].\n\n"
"```python\n"
"def find_gaps(intervals):\n"
" intervals.sort(key=lambda x: x[0])\n"
" gaps = []\n"
" \n"
" for i in range(1, len(intervals)):\n"
" if intervals[i][0] > intervals[i-1][1]:\n"
" gaps.append([intervals[i-1][1], intervals[i][0]])\n"
" \n"
" return gaps\n\n"
"# Example\n"
"print(find_gaps([[1, 5], [7, 10]])) # [[5, 7]]\n"
"```\n\n"
"---\n\n"
"### 3. **Complex Interval Operations**\n\n"
"#### a) **Interval Difference**\n\n"
"- **Problem Definition**: Given two intervals, find the difference between them, i.e., the part of the first interval that does not overlap with the second.\n\n"
"- **Approach**: \n"
" - If the intervals overlap, return the non-overlapping portions of the first interval.\n\n"
"- **Example**: \n"
" - Interval A = [1, 10], Interval B = [5, 7].\n"
" - Output: [[1, 5], [7, 10]].\n\n"
"```python\n"
"def interval_difference(A, B):\n"
" if not do_intervals_overlap(A, B):\n"
" return [A] # No overlap\n"
" \n"
" result = []\n"
" if A[0] < B[0]:\n"
" result.append([A[0], B[0]])\n"
" if A[1] > B[1]:\n"
" result.append([B[1], A[1]])\n"
" \n"
" return result\n\n"
"# Example\n"
"print(interval_difference([1, 10], [5, 7])) # [[1, 5], [7, 10]]\n"
"```\n\n"
"#### b) **Interval Scheduling**\n\n"
"- **Problem Definition**: Given a set of intervals, find the maximum number of non-overlapping intervals that can be selected.\n\n"
"- **Approach**: \n"
" - Sort intervals by end time. Greedily select intervals that do not overlap with the previously selected one.\n\n"
"- **Example**: \n"
" - Intervals = [[1, 3], [2, 4], [3, 5]].\n"
" - Output: [[1, 3], [3, 5]].\n\n"
"```python\n"
"def interval_scheduling(intervals):\n"
" intervals.sort(key=lambda x: x[1]) # Sort by end times\n"
" result = []\n"
" last_end = float('-inf')\n"
" \n"
" for interval in intervals:\n"
" if interval[0] >= last_end:\n"
" result.append(interval)\n"
" last_end = interval[1]\n"
" \n"
" return result\n\n"
"# Example\n"
"print(interval_scheduling([[1, 3], [2, 4], [3, 5]])) # [[1, 3], [3, 5]]\n"
"```\n\n"
"---\n\n"
"### 4. **Advanced Interval Challenges**\n\n"
"#### a) **Finding the Smallest Range Covering All Points**\n\n"
"- **Problem Definition**: Given several lists of intervals, find the smallest range that includes at least one interval from each list.\n\n"
"- **Approach**: \n"
" - Use a sliding window and min-heap to track the smallest range covering all lists.\n\n"
"- **Example**: \n"
" - Lists = [[1, 5], [6, 9], [7, 10]].\n"
" - Output: (6, 7).\n\n"
"```python\n"
"import heapq\n\n"
"def smallest_range(lists):\n"
" min_heap = []\n"
" max_val = float('-inf')\n"
" \n"
" # Add the first element of each list to the heap\n"
" for i, l in enumerate(lists):\n"
" heapq.heappush(min_heap, (l[0], i, 0))\n"
" max_val = max(max_val, l[0])\n"
" \n"
" min_range = float('inf'), None, None\n"
" \n"
" while min_heap:\n"
" min_val, list_idx, element_idx = heapq.heappop(min_heap)\n"
" if max_val - min_val < min_range[0]:\n"
" min_range = (max_val - min_val, min_val, max_val)\n"
" \n"
" if element_idx + 1 == len(lists[list_idx]):\n"
" break # We've reached the end of one list\n"
" \n"
" next_val = lists[list_idx][element_idx + 1]\n"
" max_val = max(max_val, next_val)\n"
" heapq.heappush(min_heap, (next_val, list_idx, element_idx + 1))\n"
" \n"
" return min_range[1], min_range[2]\n\n"
"# Example\n"
"lists = [[1, 5], [6, 9], [7, 10]]\n"
"print(smallest_range(lists)) # (6, 7)\n"
"```\n\n"
"#### b) **K-Interval Coverage**\n\n"
"- **Problem Definition**: Given a set of intervals and an integer `k`, find the maximum number of intervals that cover any point or range.\n\n"
"- **Approach**: \n"
" - Sort events (start and end of intervals), track the number of overlapping intervals at each event, and find the maximum count.\n\n"
"- **Example**: \n"
" - Intervals = [[1, 4], [2, 6], [3, 8]], k = 2.\n"
" - Output: 2.\n\n"
"```python\n"
"def max_k_interval_coverage(intervals, k):\n"
" points = []\n"
" for interval in intervals:\n"
" points.append((\n\n"
"interval[0], 'start'))\n"
" points.append((interval[1], 'end'))\n"
" \n"
" points.sort()\n"
" coverage = 0\n"
" max_coverage = 0\n"
" \n"
" for point, kind in points:\n"
" if kind == 'start':\n"
" coverage += 1\n"
" if coverage == k:\n"
" max_coverage = max(max_coverage, coverage)\n"
" else:\n"
" coverage -= 1\n"
" \n"
" return max_coverage\n\n"
"# Example\n"
"print(max_k_interval_coverage([[1, 4], [2, 6], [3, 8]], 2)) # 2\n"
"```\n\n"
"---\n\n"
"### 5. **Geometric Interval Problems**\n\n"
"#### a) **Rectangle Intersection via Intervals**\n\n"
"- **Problem Definition**: Given two rectangles, where each rectangle is defined by two intervals (x-axis and y-axis), find the intersection of these rectangles.\n\n"
"- **Approach**: \n"
" - Find the intersection of intervals on both x and y axes. The intersection of two rectangles is the combination of the intersecting intervals on both axes.\n\n"
"- **Example**: \n"
" - Rectangle A = ([1, 5], [2, 6]), Rectangle B = ([3, 7], [4, 9]).\n"
" - Output: [[3, 5], [4, 6]].\n\n"
"```python\n"
"def rectangle_intersection(A, B):\n"
" x_intersect = intersection_intervals([A[0][0], A[0][1]], [B[0][0], B[0][1]])\n"
" y_intersect = intersection_intervals([A[1][0], A[1][1]], [B[1][0], B[1][1]])\n"
" \n"
" if x_intersect and y_intersect:\n"
" return [x_intersect, y_intersect]\n"
" return None\n\n"
"# Example\n"
"A = ([1, 5], [2, 6])\n"
"B = ([3, 7], [4, 9])\n"
"print(rectangle_intersection(A, B)) # [[3, 5], [4, 6]]\n"
"```\n\n"
"---\n\n"
"This version includes **problem definitions**, **approaches**, and **examples** for all the interval problems, along with code implementations. Each section is structured to make it easier to understand and apply to similar problems.")
subst = "\\#\\1\\2"
# You can manually specify the number of replacements by changing the 4th argument
result = re.sub(regex, subst, test_str, 0, re.MULTILINE)
if result:
print (result)
# Note: for Python 2.7 compatibility, use ur"" to prefix the regex and u"" to prefix the test string and substitution.
Please keep in mind that these code samples are automatically generated and are not guaranteed to work. If you find any syntax errors, feel free to submit a bug report. For a full regex reference for Python, please visit: https://docs.python.org/3/library/re.html