LeetCode Daily Problem P3508 Design a Router

---

Timeline

Timeline

2025-09-20

init

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

---

Problem:

P3508 Design a Router

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

This problem is prone to timeouts, mainly because the timestamps are inherently ordered. If you treat them as unordered, you will basically time out. For example, using a multiset to store timestamps to keep them ordered, but actually a simple vector is sufficient.

Note the std::distance function. Some iterators do not support subtraction, so you can only use this to calculate the distance.

Note that if std::set stores a class or struct, you must implement the comparison operator, because set is ordered.

• std::lower_bound
  • Purpose: Returns an iterator to the first element that is greater than or equal (>=) to the specified value. - If the value exists: returns the first position of that value. - If the value does not exist: returns the position of the first element greater than the target value. - If all elements are less than the target value: returns the end() iterator.

    Reverse lookup for elements less than the target value: std::lower_the iterator returned by bound minus one, i.e., std::lower_bound(vec.begin(), vec.end(), target) - 1。

• std::upper_bound
  • Purpose: Returns an iterator to the first element greater than (>) the specified value. - If the value exists: skips all equal values and returns the position of the first element greater than the target value. - If the value does not exist: returns the position of the first element greater than the target value. - If all elements are less than or equal to the target value: returns the end() iterator.

    Reverse lookup for elements less than or equal to the target value: std::upper_the iterator returned by bound minus one, i.e., std::upper_bound(vec.begin(), vec.end(), target) - 1。

Note: when writing operator<

• The parameter must be const Movie& (cannot accept non-const reference).
• The function itself must be const (it will not modify *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);
 */