leetcode每日一题 P3508 设计路由器

---

时间轴

时间轴

2025-09-20

init

std::set std::distance std::lower_bound std::upper_bound

---

题目：

P3508 设计路由器

https://leetcode.cn/problems/implement-router/description/?envType=daily-question&envId=2025-09-20

这题很容易超时，主要是因为这个时间本来就是有序的，如果认为是无序的那么基本就超时了，比如用 multiset 存 timestamp 以求其有序，但实际上用简单的 vector 存就行。

注意 std::distance 这个函数，有的迭代器不支持减法只能用这个求其距离

注意 std::set 如果存入 class 或者 struct 那么得实现比较的 operator,因为 set 是有序的

• std::lower_bound
  • 作用: 返回第一个 大于等于 (>=) 指定值的元素的迭代器。 - 如果值存在: 返回该值的第一个位置。 - 如果值不存在: 返回比目标值 大的第一个元素 位置。 - 如果所有元素都小于目标值: 返回 end() 迭代器。

    反向查找小于目标值的元素: std::lower_bound 返回的迭代器减一，即 std::lower_bound(vec.begin(), vec.end(), target) - 1。

• std::upper_bound
  • 作用: 返回第一个 大于 (>) 指定值的元素的迭代器。 - 如果值存在: 跳过所有相同值，返回比目标值 大的第一个元素 位置。 - 如果值不存在: 返回比目标值 大的第一个元素 位置。 - 如果所有元素都小于等于目标值: 返回 end() 迭代器。

    反向查找小于等于目标值的元素: std::upper_bound 返回的迭代器减一，即 std::upper_bound(vec.begin(), vec.end(), target) - 1。

注意 写 operator<时

• 参数必须是 const Movie&（不能接受非 const 引用）
• 函数本身必须是 const（不会修改 *this）

#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <vector>

using std::map;
using std::queue;
using std::set;
using std::vector;

class Packet {
public:
  int source;
  int destination;
  int timestamp;
  bool operator<(const Packet &other) const {
    if (destination != other.destination)
      return destination < other.destination;
    if (timestamp != other.timestamp)
      return timestamp < other.timestamp;
    return source < other.source;
  }
};

class Router {
private:
  set<Packet> router_set;
  queue<Packet> fifo;
  // destination->[timestamp array]
  map<int, vector<int>> router_map;
  int memoryLimit;

public:
  Router(int memoryLimit) { this->memoryLimit = memoryLimit; }

  bool addPacket(int source, int destination, int timestamp) {
    struct Packet newPacket = {source, destination, timestamp};

    if (router_set.find(newPacket) != router_set.end()) {
      return false;
    }

    if (router_set.size() >= memoryLimit ||
        fifo.size() >= memoryLimit) { // out of memory
      Packet s = fifo.front();
      fifo.pop();
      router_set.erase(s);
      vector<int> &timestamp_array = router_map[s.destination];
      timestamp_array.erase(
          find(timestamp_array.begin(), timestamp_array.end(), s.timestamp));
    }

    router_set.insert(newPacket);
    fifo.push(newPacket);

    router_map[destination].push_back(timestamp);

    return true;
  }
  vector<int> forwardPacket() {
    vector<int> res;
    if (fifo.empty()) {
      return {};
    }

    Packet resPacket = fifo.front();
    fifo.pop();
    res = {resPacket.source, resPacket.destination, resPacket.timestamp};
    router_set.erase(resPacket);

    vector<int> &timestamp_array = router_map[resPacket.destination];
    timestamp_array.erase(find(timestamp_array.begin(), timestamp_array.end(),
                               resPacket.timestamp));
    return res;
  }

  int getCount(int destination, int startTime, int endTime) {
    vector<int> &vec = router_map[destination];
    return std::distance(std::lower_bound(vec.begin(), vec.end(), startTime),
                         std::upper_bound(vec.begin(), vec.end(), endTime));
  }
};

/**
 * Your Router object will be instantiated and called as such:
 * Router* obj = new Router(memoryLimit);
 * bool param_1 = obj->addPacket(source,destination,timestamp);
 * vector<int> param_2 = obj->forwardPacket();
 * int param_3 = obj->getCount(destination,startTime,endTime);
 */