from typing import List


def merge(intervals: List[List[int]]) -> List[List[int]]:
    """
    Time complexity: O(N * log(N))
    Space complexity: O(N)

    Parameters
    ----------
    intervals : List[List[int]]
        input intervals

    Returns
    -------
    merged : List[List[int]]
        merged intervals

    """
    merged = []
    intervals.sort(key=lambda x: x[0])
    for i in range(len(intervals)):
        if not merged or intervals[i][0] > intervals[i - 1][1]:
            merged.append(intervals[i])
        else:
            merged[-1][1] = max(merged[-1][1], intervals[i][1])
    return merged