Linear solution without sorting or map for fun


  • 0
    M

    Hey guys, I saw tons of solutions with sorting the intervals, here's a linear solution, this solution may not be more efficient than the sorting solution, but it will have a good performance if the number of intervals is huge while the full time line is not that long.
    The code is straight forward. Please feel free to correct me if anywhere goes wrong.

    N: number of intervals
    M: the length of whole time line
    time complexity is O(N + M)
    space is O(M)
    timeline[i] : the number of meetings at the same time i

    bool canAttendMeetings(vector<Interval>& intervals) {
            int largestTimeStamp = 0;
            for(Interval i : intervals){
                largestTimeStamp = max(largestTimeStamp, i.end);
            }
            vector<int> timeline (largestTimeStamp + 1, 0);
            for(Interval i : intervals){
                timeline[i.start]++;
                timeline[i.end]--;
            }
            for(int i = 1; i <= largestTimeStamp; ++i){
                timeline[i] += timeline[i - 1];
                if(timeline[i] > 1){
                    return false;
                }
            }
            return true;
        }
    

Log in to reply
 

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