Simple sorted solution


  • 0
    R

    Usually people don't use C here, but here's one solution with C

    int cmpfunc(void *a, void *b) {
        return (((struct Interval *)a)->start - ((struct Interval *)b)->start);
    }
    
    /**
     * Return an array of size *returnSize.
     * Note: The returned array must be malloced, assume caller calls free().
     */
    struct Interval* merge(struct Interval* intervals, int intervalsSize, int* returnSize) {
        int i = 0;
        int j = 0;
        struct Interval *rc = (struct Interval *)malloc(sizeof(struct Interval)*intervalsSize);
        qsort(intervals, intervalsSize, sizeof(struct Interval), cmpfunc);
     
        for (i = 0; i < intervalsSize; i++) {
            if ((i > 0) && (rc[j-1].start <= intervals[i].start) && (rc[j-1].end >= intervals[i].start)) {
                rc[j-1].start = rc[j-1].start < intervals[i-1].start ? rc[j-1].start : intervals[i-1].start;
                rc[j-1].end = intervals[i].end > rc[j-1].end ? intervals[i].end : rc[j-1].end;
            } else {
                rc[j].start = intervals[i].start;
                rc[j].end = intervals[i].end;
                j++;
            }
        }
        
        (*returnSize) = j;
        return (rc);
    }
    
    

Log in to reply
 

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