一、题目信息

今天来做450这个题目把，主要考察的利用空间换时间，查询从o(n),优化到o(1)

  • 如果能用方法1实现，说明能把时间抽象成一个点.而不是一个间距。我刚开始就疑惑为啥root房间问题直接给出开始时间和结束时间，而是给出2个vector，多此一举。 目的告诉你查询 queryTime也是一个时间点。我纠结在一天24小时，一小时 60分钟，有一分钟 60秒，毫秒，无穷无尽呀！ startTime[i] <= endTime[i] <= 1000

  • 如果能用方法2实现，说明理解了多个非线性点在空间上分布，就是离线的，推荐一本书 «离散数学及其应用»。 做什么事情都讲究概率的。例如身高服从正态分布(泊松分布),财富分配二八定律(幂律分布)，扯远了。 提示 queryTime <= 1000，空间也是有限的。

  • 链接：1450. 在既定时间做作业的学生人数
  • 来源：Interview Question
  • 难度：Easy

二、题目描述

算法是问题求解过程的一种描述，看看这个题目是怎么描述的吧。

1
2
3
4
5
6

提示

startTime.length == endTime.length
1 <= startTime.length <= 100
1 <= startTime[i] <= endTime[i] <= 1000
1 <= queryTime <= 1000

三、算法描述

能说出基本思想即可,实在不行动手画个流程图把。

  • For multiple queries: image.png image.png

四、参考代码

放轻松，虽然是c++实现，我们一贯宗旨是拒绝奇技淫巧，不懂代码一看就明白

c++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
public:

    /***
     1 解题思路1：
       正确理解题意，查询[startTime[i], endTime[i]]内 包含queryTime有多个区间。
       我上来被题目描述看这么多字，然后放弃了。
     2.算法描述：
      一次性那遍历，判断queryTime >= startTime[i] && queryTime <= endTime[i]个数。

     3.复杂度：时间 O(N),空间O(1)
    ***/
    int busyStudent(vector<int>& startTime, vector<int>& endTime, int queryTime) {
      
      int length=startTime.size(); //题目给出条件  startTime.length == endTime.length
      
      int res =0;//时间 抽象成一个整数 例如时间戳， 查询时间也是时间戳。不考虑时间段问题。
      //queryTime 处于区间 [startTime[i], endTime[i]]（含）的学生人数。

      for(int i=0;i<length;i++)
      {
        if (queryTime >= startTime[i] && queryTime <= endTime[i])
        {
           res++;
        }
      }
      return res;

    }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

class Solution
{
public:

    /***
     1 解题思路2：
       因为查询时间点，是有限的，开始时间和结束时间也是有点的 不超过1000个
       直接计算[0-1001]个点直接 全部同时学习的学生。
       For multiple queries:
       We can calculate the overlapping intervals at any time by maintaining an array that contains the intervals of all the students. 
       Doing this requires O(maxm_element + numberOfStudents) time.
     2.算法描述：
       1. 用开始时间，作为数组下标，遍历开始时间数组。count[start] += 1;
       2. 用结束时间，作为数组下标，遍历结束时间数组。 count[end + 1] -= 1;
       3. 累加：count[i] += count[i - 1];
     3.复杂度：时间 O(N),空间O(N)
    int busyStudent(vector<int> &startTime, vector<int> &endTime, int queryTime)
    {

        //作为一个服务,这里假如每次查询 startTime,endTime固定不变，变化的queryTime.
        // 如果每次startTime，endTime都是变化的，这个算法浪费空间了.
        vector<int> count(1002, 0); //key 时间点，value 10002是防止end+1越界，[0--1001]

        for (auto start : startTime)
        {
            count[start] += 1;
        }

        for (auto end : endTime)
        {
            count[end + 1] -= 1;
        }
        //[1,100],[2,100],[3,100],[4,100] 在4点，100点同时多少个学生在学习,答案就是4.在101点呢，都结束了。
        for (int i = 1; i < 1002; i++)
        {
            count[i] += count[i - 1];
        }

        return count[queryTime];
    }
};

go

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

func busyStudent(startTime []int, endTime []int, queryTime int) int {
 
    length:=len(startTime)
    res:=0
    for i:=0;i<length;i++{
       if queryTime>=startTime[i] &&  queryTime <=endTime[i] {
           res++
       }
    }

    return res;

}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution {

public:
    int busyStudent(vector<int>& startTime, vector<int>& endTime, int queryTime) {
      
      //作为一个服务,这里假如每次查询 startTime,endTime固定不变，变化的queryTime.
      // 如果每次startTime，endTime都是变化的，这个算法浪费空间了.
      vector<int>count(1002,0);//key 时间点，value 10002是防止end+1越界，[0--1001]

      for(auto start:startTime)
      {
        count[start]+=1;
      }

      for(auto end:endTime)
      {
        count[end+1]-=1;
      }
      //[1,100],[2,100],[3,100],[4,100] 在4点，100点同时多少个学生在学习,答案就是4.在101点呢，都结束了。
      for(int i=1;i<1002;i++)
      {
        count[i]+=count[i-1];
      }


      return count[queryTime];
    }

    
};

五、举一反三

别人最佳答案并不重要，关键是自己理解。

1897-meeting-room-ii

1
2
3
4
5
6

输入: intervals = [(0,30),(5,10),(15,20)]
输出: 2
解释:
需要两个会议室
会议室1:(0,30)
会议室2:(5,10),(15,20)