Simple, clean solution in cpp


  • 0
    N

    The idea is to sort the intervals in the order of increasing starting time.
    Intuition - Like in real life, we start allotment from the earliest starting meeting. For each new meeting we go see earlier scheduled rooms in the allotted order. If no already allotted suitable room is found, we allocate a new room.

    class Solution {
    public:
        struct Compare
        {
            bool operator()(const Interval &one, const Interval &two)
            {
                return one.start < two.start;
            }
        }compare;
        int minMeetingRooms(vector<Interval>& intervals) {
            std::sort(intervals.begin(), intervals.end(), compare);
            // rooms store the ending time of the meeting scheduled in this room.
            std::vector<int> rooms;
            for (int i = 0; i < intervals.size(); i++)
            {
                bool room_found = false;
                for (int j = 0; j < rooms.size(); j++)
                {
                    if (intervals[i].start >= rooms[j])
                    {
                        rooms[j] = intervals[i].end;
                        room_found = true;
                        break;
                    }
                }
                if (room_found == false)
                    rooms.push_back(intervals[i].end);
            }
            return rooms.size();
        }
    };
    

Log in to reply
 

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