Merging Overlapping Intervals

When dealing with a colection of intervals, the objective is to consolidate all overlapping segments into a single continuous range. The most efficient approach involves sorting the intervals by their starting points. This ensures that we only need to compare the current interval with the last processed interval in our results.

def merge_intervals(intervals):
    if not intervals:
        return []

    # Organize intervals by their starting boundary
    intervals.sort(key=lambda x: x[0])
    
    consolidated = [intervals[0]]

    for i in range(1, len(intervals)):
        current_start, current_end = intervals[i]
        last_added_end = consolidated[-1][1]

        # If the current interval overlaps with the last one, extend the boundary
        if current_start <= last_added_end:
            consolidated[-1][1] = max(last_added_end, current_end)
        else:
            # Otherwise, add it as a new distinct interval
            consolidated.append([current_start, current_end])
            
    return consolidated

Constructing the Largest Monotone Increasing Number

To find the largest integer less than or equal to N that features digits in non-decreasing order, a greedy strategy is applied from right to left. If a digit is found to be greater than the digit to its immediate right, the current digit is decremented, and all subsequent digits to the right are set to '9' to maximize the resulting value.

def monotone_increasing_digits(num):
    digits = list(str(num))
    length = len(digits)
    # Mark where the sequence of '9's should begin
    start_nine = length 

    for i in range(length - 1, 0, -1):
        if digits[i - 1] > digits[i]:
            digits[i - 1] = str(int(digits[i - 1]) - 1)
            start_nine = i

    for i in range(start_nine, length):
        digits[i] = '9'

    return int("".join(digits))

Minimizing Camera Placement in Binary Trees

In a binary tree surveillance problem, the goal is to place the minimum number of cameras such that every node is monitored. A camera covers itself, its parent, and its immediate children.

To optimize placement, we avoid placing cameras on leaf nodes. Instead, we place them on the parents of leaf nodes, which allows the camrea's coverage to extend further up the tree. This bottom-up approach is implemented using a post-order traversal.

Node States:

• 0: Node is not covered.
• 1: Node has a camera installed.
• 2: Node is covered by a camera elsewhere.

class Solution:
    def min_camera_cover(self, root):
        self.camera_count = 0
        
        def post_order_eval(node):
            # Base case: null nodes are considered covered (state 2)
            if not node:
                return 2
            
            left_state = post_order_eval(node.left)
            right_state = post_order_eval(node.right)

            # If any child is not covered, the current node must host a camera
            if left_state == 0 or right_state == 0:
                self.camera_count += 1
                return 1
            
            # If any child has a camera, the current node is covered
            if left_state == 1 or right_state == 1:
                return 2
            
            # If both children are covered (but have no camera), current node is uncovered
            return 0

        # If the root is left uncovered by its children, add a camera at the root
        if post_order_eval(root) == 0:
            self.camera_count += 1
            
        return self.camera_count