Simple Cpp methon using 24ms beats 100%


  • 0
    X

    My method is to use two arrays :start and end to store each Interval's start and end,and sort them by inc order.
    so i don't need to concern the relation among these starts and end ,i only concern the interval num at a certain time.
    for example:

    from 2,6 1,3 8,10 wo got two sorted arrays [1,2,8] and [3,6,10]
    we ini the cnt =0;
    we compare them like this [1,2,3,6,8,10] (we dongt need to put them in a real array,just know the pos is ok)
    when we met a start cnt++ and record start when the original cnt is 0;
    when we met a end cnt-- and record the end when the cnt is 0, add the (start,end) to the return list.

    /**
     * Definition for an interval.
     * struct Interval {
     *     int start;
     *     int end;
     *     Interval() : start(0), end(0) {}
     *     Interval(int s, int e) : start(s), end(e) {}
     * };
     */
    class Solution {
    public:
        vector<Interval> merge(vector<Interval>& intervals) {
            int is = intervals.size();
            vector<int> start(intervals.size());
            vector<int> end(intervals.size());
            vector<Interval> ret;
            for(int i=0;i<is;i++)
            {
                start[i] = intervals[i].start;
                end[i] = intervals[i].end;
            }
            sort(start.begin(),start.end());
            sort(end.begin(),end.end());
            int count=0;
            int t_start=0;
            Interval t_int;
            start.push_back(99999);
            end.push_back(99999);
            for(int i =0,j=0;i<=is&&j<=is;)
            {
                if(start[i] <= end[j])
                {
                    if(count ==0)
                    {
                        t_start =  start[i];
                        count++;
                    }
                    else
                    {
                        count++;
                    }
                    i++;
                }
                else
                {
                    count--;
                    
                    if(count == 0)
                    {
                        t_int.start = t_start;
                        t_int.end = end[j];
                        ret.push_back(t_int);
                    }
                    j++;
                }
            }
            return ret;
        }
    };

Log in to reply
 

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