<jupyter_start><jupyter_text>Does it "stab"? Let X be a set of n intervals on the real line. We say that a set of points P "stabs" X if every interval in X contains at least one point in P. Compute the smallest set of points that stabs X.For example, given the intervals [(1, 4), (4, 5), (7, 9), (9, 12)], you should return [4, 9].<jupyter_code>from itertools import combinations

def get_points(intervals): 
    points = set([element for pair in intervals for element in pair])
    
    subsets = [] 
    for size in range(1, len(points)): 
        subsets.extend(list(combinations(points,sizez)))
        
    for start, end in intervals: 
        for subset in subsets: 
            
            # is there a point that is btwn the start and end of all intervals
            if all(any(start <= point <= end for point in subset)
                  for start, end in intervals): 
                return subset<jupyter_output><empty_output><jupyter_text>Very inefficient. $O(2^N)$ subsetsFor each one we are matching its points against every interval start and endpoint.  So this is actually $O(2^N * N^2)$ Yikes...An optimal greedy strategy exists. First you have to ...- sort the intervals in ascending endpoint- traverse the list... whenever you find an interval not "stabbed" by any points in our solution, take its endpoint and add it to our solution- since intervals are sorted, consider the most recently added endpoint to determine if there's an intersection<jupyter_code>def get_points(intervals): 
    intervals.sort(key=lambda x: (x[1], x[0]))
    
    points = [] 
    latest_endpoint = None
    
    for start, end in intervals: 
        if start <= latest_endpoint: 
            continue
        else: 
            points.append(end)
            latest_endpoint = end
            
    return points<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.08089033659066232, 'fraction_numerical': 0.009229098805646038, 'mean_word_length': 2.8078512396694215, 'pattern_counts': {'":': 0, '<': 12, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '68487', 'license': 'MIT', 'n_tokens_mistral': 524, 'n_tokens_neox': 493, 'n_words': 224, 'path': 'Daily/Overlap aka stab.ipynb', 'repo_name': 'jasonyum/python_go', 'size': '1842'}