美文网首页
252.Meeting Rooms

252.Meeting Rooms

作者: 丁不想被任何狗咬 | 来源:发表于2016-05-09 22:44 被阅读121次

    1.Meeting-rooms https://leetcode.com/problems/meeting-rooms/
    2.Meeting-rooms ii https://leetcode.com/problems/meeting-rooms-ii/

    1.Meeting-rooms
    https://leetcode.com/problems/meeting-rooms/
    先排序再遍历

    /**
     * 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:
        bool canAttendMeetings(vector<Interval>& intervals) {
            if(intervals.empty()) {
                return true;
            }
            sort(intervals.begin(),intervals.end(),[](Interval &a, Interval &b){ return a.start < b.start;});
            int last = intervals.front().end;
            for(int i = 1; i < intervals.size(); i++) {
                if(intervals[i].start < last) {
                    return false;
                }
                last = intervals[i].end;
            }
            return true;
        }
    };
    

    2.Meeting-rooms ii https://leetcode.com/problems/meeting-rooms-ii/
    计算最少需要多少个room。

    class Solution {
    public:
        int minMeetingRooms(vector<Interval>& intervals) {
            sort(intervals.begin(),intervals.end(), cmp);
            vector<int> rooms;
            bool noRoomFlag;
            for(auto &i: intervals) {
                noRoomFlag = true;
                for(auto &r: rooms){
                    if(r <= i.start) { //<=
                        r = i.end;
                        noRoomFlag = false;
                        break;
                    }
                }
                if(noRoomFlag) {
                    rooms.push_back(i.end);
                }
            }
            return rooms.size();
        }
    
        static bool cmp(Interval &a, Interval &b) {
            return a.start < b.start || (a.start == b.start && a.end < b.end);
        }
    };

    相关文章

      网友评论

          本文标题:252.Meeting Rooms

          本文链接:https://www.haomeiwen.com/subject/igberttx.html