253会议室 II

本是古典何须时尚 2023-02-08 15:52 12阅读 0赞

# 一、前言 #

标签：区间有序化、上下车问题。

问题来源LeetCode 253 难度：中等。

问题链接：[https://leetcode-cn.com/problems/meeting-rooms-ii/][https_leetcode-cn.com_problems_meeting-rooms-ii]

## 二、题目 ##

给定一个会议时间安排的数组，每个会议时间都会包括开始和结束的时间 \[\[s1,e1\],\[s2,e2\],...\] (si < ei)，为避免会议冲突，同时要考虑充分利用会议室资源，请你计算至少需要多少间会议室，才能满足这些会议安排。

**示例1：**

输入: [[0, 30],[5, 10],[15, 20]]
    输出: 2

**示例2：**

输入: [[7,10],[2,4]]
    输出: 1

## 三、思路 ##

提供两种解题方法。

方法一：区间有序化。先对区间进行排序，然后根据相邻区间前后时间对比进行统计需要的会议上。

例如，输入：\[\[0, 30\],\[5, 10\],\[15, 20\]\]

1.  有序化之后：\[\[0, 30\],\[5, 10\],\[15, 20\]\]
2.  定义变量ans用于统计需要的会议上个数，定义变量st用于统计使用的会议上最晚结束时间
3.  对于\[0,30\]，由于是第一个需要一个会议上，此时ans = 1, st = \{30\}
4.  对于\[5,10\]，st中30大于5，会议无法重用，此时ans = ans+1 = 2, st = \{30,10\}
5.  对于\[15,20\]，st中10不大于5，会议可以重用，此时ans = 2, st = \{30,20\}
6.  最终结果 ans = 2

方法二：上下车问题。可以将这个问题转换为上下车问题，不用在意是谁上车还是下车，只需要注意什么时候上下车就可以。 以第一个示例来说：

![20200725102507276.png][]

核心思路：上车的最大人数就是会议室占用的最大间数。将上车和下车时间点混合排序

1.  当上车1个人时，count++
2.  当下车1个人时，count--
3.  每次上下车时，取maxvalue = max(maxvalue, count);
4.  最终结果 maxvalue = 2

## 四、总结 ##

*  当看到有区间，首先需要想到是否需要对区间进行排序，再看排序之后怎样处理符合题意。
 *  思路转换，例如方法二，这种转换方式，值得回味思考学习。

## 四、编码实现 ##

//==========================================================================
    /*
    * @file    : 253_MinMeetingRooms.h
    * @label   : 区间有序化、上下车问题
    * @blogs   : https://blog.csdn.net/nie2314550441/article/details/107574875
    * @author  : niebingyu
    * @date    : 2020/07/25
    * @title   : 253.会议室 II
    * @purpose : 给定一个会议时间安排的数组，每个会议时间都会包括开始和结束的时间 [[s1,e1],[s2,e2],...] (si < ei)，
    * 为避免会议冲突，同时要考虑充分利用会议室资源，请你计算至少需要多少间会议室，才能满足这些会议安排。
    *
    * 示例1：
    * 输入: [[0, 30],[5, 10],[15, 20]]
    * 输出: 2
    *
    * 示例2：
    * 输入: [[7,10],[2,4]]
    * 输出: 1
    *
    * 来源：力扣（LeetCode）
    * 难度：中等
    * 链接：https://leetcode-cn.com/problems/meeting-rooms-ii/
    */
    //==========================================================================
    #pragma once
    #include <iostream>
    #include <vector>
    #include <set>
    #include <algorithm>
    #include <assert.h>
    using namespace std;
    
    #define NAMESPACE_MINMEETINGROOMS namespace NAME_MINMEETINGROOMS {
    #define NAMESPACE_MINMEETINGROOMSEND }
    NAMESPACE_MINMEETINGROOMS
    
    // 方法一，区间有序化
    class Solution_1 
    {
    public:
        int minMeetingRooms(vector<vector<int>>& intervals) 
        {
            if (intervals.size() <= 1)
                return intervals.size();
            
            // 默认传入的参数正确
            sort(intervals.begin(), intervals.end(),
                [](const vector<int>& l, const vector<int>& r) { return l[0] < r[0] || (l[0] == r[0] && l[1] < r[1]); });
    
            int ans = 1;
            set<int> st;
            st.insert(intervals[0].back());
            for (int i = 1; i < intervals.size(); ++i)
            {
                auto it = st.begin();
                if (intervals[i][0] < *it)  ++ans;
                else st.erase(it);
                st.insert(intervals[i][1]);
            }
    
            return ans;
        }
    };
    
    // 方法二，上下车
    class Solution_2 
    {
    public:
        int minMeetingRooms(vector<vector<int>>& intervals) 
        {
            if (intervals.empty()) 
                return 0;
    		
            vector<pair<int,int>> meeting;
            for(auto interval:intervals)
            {
                meeting.push_back(pair<int, int>(interval[0], 1));
                meeting.push_back(pair<int, int>(interval[1], -1));
            }
    
            sort(meeting.begin(), meeting.end(), [](const pair<int, int>& l, const pair<int, int>& r) 
                { return l.first < r.first || (l.first == r.first && l.second < r.second); });
    
            int cnt = 0, maxvalue = 0;
            for(auto meet:meeting)
            {
                cnt += meet.second;
                maxvalue = max(maxvalue, cnt);
            }
    
            return maxvalue;
        }
    };
    
    以下为测试代码//
    // 测试 用例 START
    void test(const char* testName, vector<vector<int>>& intervals, int expect)
    {
        Solution_1 s1;
        int result1 = s1.minMeetingRooms(intervals);
        Solution_2 s2;
        int result2 = s2.minMeetingRooms(intervals);
    
        if (result1 == expect && result2 == expect)
            cout << testName << ", solution passed." << endl;
        else
            cout << testName << ", solution failed. " << endl;
    }
    
    // 测试用例
    void Test1()
    {
        vector<vector<int>> intervals = { {0, 30} ,{5, 10},{15, 20} };
        int expect = 2;
        test("Test1()", intervals, expect);
    }
    
    void Test2()
    {
        vector<vector<int>> intervals = { {7, 10} ,{2, 4} };
        int expect = 1;
        test("Test2()", intervals, expect);
    }
    
    void Test3()
    {
        vector<vector<int>> intervals = { {1, 5} ,{8, 9},{8, 9} };
        int expect = 2;
        test("Test3()", intervals, expect);
    }
    NAMESPACE_MINMEETINGROOMSEND
    // 测试 用例 END
    //
    void MinMeetingRooms_Test()
    {
        cout << "------ start 253.会议室 II ------" << endl;
        NAME_MINMEETINGROOMS::Test1();
        NAME_MINMEETINGROOMS::Test2();
        NAME_MINMEETINGROOMS::Test3();
        cout << "------ end 253.会议室 II --------" << endl;
    }

**执行结果：**

![2020072510261468.png][]

[https_leetcode-cn.com_problems_meeting-rooms-ii]: https://leetcode-cn.com/problems/meeting-rooms-ii/
[20200725102507276.png]: /images/20230208/efb6aafa54384f5b91512d68e4a9fafa.png
[2020072510261468.png]: /images/20230208/bea51a4a96a04482b6e31e22e05d6fe8.png