C, 4mS O(n)


  • 0
    M

    We can simply scan from both the ends looking for the correct location. Basic idea is to narrow down the set of interval entries which will be deleted and merged into one because of the insertion.

    For example: Consider inserting {4, 9} into the array {1, 2}, {3, 5}, {6, 7}, {8, 10}, {12, 16}, here after the scan the variable i would be 1 and j will be 3. At this point we can collapse the three entries at offset 1, 2, and 3 into one -- {3, 10}

    struct Interval* insert(struct Interval* intervals, int intervalsSize,
                            struct Interval newInterval, int* returnSize)
    {
        struct Interval *it = intervals, *nt = &newInterval;
        int len = intervalsSize, i, j;
        struct Interval *nit;
    
        /* Allocate space */
        nit = malloc(sizeof(struct Interval) * (len + 1));
        if (!nit)
            return NULL;
    
        /* Seek the interval start location. Also, while we are at it,
           copy the contents to the new array */
        for(i = 0; (i < len) && (it[i].end < nt->start); ++i)
            copy_interval(&nit[i], &it[i]);
    
        /* Traverse the array from the end seeking the interval
           end location */
        for (j = len - 1; j >= 0 && it[j].start > nt->end; --j);
    
        /* If there is a need to merge the ranges, then do the same. */
        if (j >= i)
        {
            /* Pick the smaller start offset */
            nt->start = (i < len && it[i].start > nt->start) ?
                         nt->start : it[i].start;
    
            /* Pick the greater end offset */
            nt->end = (j >= 0 && j < len && it[j].end > nt->end) ?
                       it[j].end : nt->end;
        }
    
        /* Update the offsets and copy the remaining elements */
        j = (j < i) ? i : j + 1;
        copy_interval(&nit[i++], nt);
        while (j < len)
            copy_interval(&nit[i++], &it[j++]);
    
        /* Set the return size */
        *returnSize = i;
        return nit;
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.