Easy C++ Solution with Explanations


  • 16

    The idea is pretty simple: first we sort the intervals in the ascending order of start; then we check for the overlapping of each pair of neighboring intervals. If they do, then return false; after we finish all the checks and have not returned false, just return true.

    Sorting takes O(nlogn) time and the overlapping checks take O(n) time, so this idea is O(nlogn) time in total.

    The code is as follows.

    class Solution {
    public:
        bool canAttendMeetings(vector<Interval>& intervals) {
            sort(intervals.begin(), intervals.end(), compare);
            int n = intervals.size();
            for (int i = 0; i < n - 1; i++)
                if (overlap(intervals[i], intervals[i + 1]))
                    return false;
            return true;
        }
    private:
        static bool compare(Interval& interval1, Interval& interval2) {
            return interval1.start < interval2.start;
        }
        bool overlap(Interval& interval1, Interval& interval2) {
            return interval1.end > interval2.start;
        } 
    };

  • 7
    J
    class Solution {
    public:
        bool canAttendMeetings(vector<Interval>& intervals) {
            sort(intervals.begin(),intervals.end(),[](const Interval &a,const Interval &b){return a.start<b.start;});
            for(int i=0;i<(int)intervals.size()-1;++i)
                if(intervals[i].end>intervals[i+1].start)return false;
            return true;
        }
    };
    

    Simplify your code


  • 1

    Hi, jiannan. I have seen the great C++ 11 features in your code :-) Thanks for your great simplification.

    BTW, a simple remind, I guess it would be much safer to write (int)intervals.size() - 1. Otherwise if intervals.size() == 0, since it is an unsinged int, minus by 1 will not give -1 and the code may meet runtime error.


  • 0
    S

    Nice and clean :)


  • 0
    J

    Yup, thanks for the advice.


  • 0
    E

    I know we have to use static. but why static for static bool compare?
    Please let me know. thanks


  • 0
    W

    @jianchao.li.fighter Another solution without using sort, but still bears the same O(NlogN) complexity.

    bool canAttendMeetings(vector<Interval>& intervals) {
            auto mycomp = [&](const Interval& i1, const Interval& i2) {return i1.end <= i2.start;};
            set<Interval, decltype(mycomp)> myset(mycomp);
            for(auto& inter: intervals)
                if(!myset.insert(inter).second) return false;
            return true;
        }
    

  • 0
    Z

    @jianchao.li.fighter
    How about starting from i = 1, and compare intervals[i] and interval[i-1] :)


  • 0
    B

    I have two questions with regard to this problem. I tried to remove the static key word, and it won't pass, any suggestions?

    And within the for loop, if we directly use for(int i=0; i<Intervals.size()-1; i++) , it won't work as well. We must declare n=Intervals.size() first. Why..? It looks very confusing to me.


Log in to reply
 

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