763. Partition Labels

from collections import defaultdict
class Range:
    def __init__(self):
        self.start = None
        self.end = None
        self.char = None
    def __repr__(self):
        return '(' + self.char + ':' + str(self.start) + '->' + str(self.end) + ')'
class Solution:
    def partitionLabels(self, S: str) -> List[int]:
        '''
        
        Input:
            S - lowercase letters.
        Return:
            partition - int[]. each integer represents the size of each partition
            I want to create as many partitions as possible.
        Constraint:
            A letter has to appear in the same partition.
            
        Example:
            ababcbacadefegdehijhklij
            ---------
             -----
                ----
                     ------
                      ------
        Def'n:
            Partition:
                Operates on collections of items.
                The partition splits this collection into many smaller collections.
                    Based on a criteria.
                
            Uses:
                Find K'th item:
                    Using Lomuto Partitioning which sandwiches a pivot.
                    The criteria for forming the partitions are <= pivot and >= pivot.
                Sorting:
                    Either use Lomuto or Hoare to recursively partition array based on criteria.
                    Hoare:
                        Splits array into <= to partition and >= partition.
                        Does NOT sandwich the given pivot between the partitions.
                Given overlapping ranges, we can partition a list such that the partition doesn't cut a range.
        Approach:
            Union-Find?:
                Find the range of each letter.
                If a range of 'A' overlaps with range of 'B' your partition cannot be in these ranges
                
                Start merging ranges until you cannot anymore.
            Merge Interval:
                1. Generate all intervals in linear time.
                    Use Hash
                2. Sort by start time.
                3. Generate merged intervals
                4. Return lengths of each interval.
        '''
        
        # Step 1 - Generate intervals
        intervals = defaultdict(Range)
        for idx, char in enumerate(S):
            # Check if interval is NEW
            if intervals[char].start is None:
                intervals[char].start = idx
                intervals[char].end = idx
                intervals[char].char = char
                continue
            # Interval was already defined
            intervals[char].end = idx
        
        # Step 2 - Sort by start time. I think defaultdict works.
        
        # Step 3 - Generate Merge intervals.
        '''
        ----------
        
        ---------
            ---------
            
        ---------
                    -------
        '''
        intervalList = list(intervals.values())
        mergedLengths = []
        
        # temporary interval
        start = intervalList[0].start
        end = intervalList[0].end
        
        for idx, interval in enumerate(intervalList):
            if idx == 0:
                continue
            
            # I need to check the relationship between 'interval' and start/end.
            
            # Do they overlap
            if interval.start < end:
                end = max(end, interval.end)
                continue
            
            # They DO NOT overlap
            mergedLengths.append(end - start + 1)
            start = interval.start
            end = interval.end
        
        mergedLengths.append(end - start + 1)
        
        return mergedLengths
            
        '''
        ---------
              -------
              
        ---------
                    ---------
        '''