3433. Count Mentions Per User

• Time: $O(n\log n)$
• Space: $O(n)$

C++JavaPython

struct OfflineUser {
  int returnTimestamp;
  int userId;
  bool operator>(const OfflineUser& other) const {
    return returnTimestamp > other.returnTimestamp;
  }
};

class Solution {
 public:
  vector<int> countMentions(int numberOfUsers, vector<vector<string>>& events) {
    vector<int> ans(numberOfUsers);
    vector<int> online(numberOfUsers, true);
    // min-heap to track users that are offline
    priority_queue<OfflineUser, vector<OfflineUser>, greater<>> offlineQueue;
    int allMentionsCount = 0;

    ranges::sort(events, ranges::less{}, [](const vector<string>& event) {
      const int timestamp = stoi(event[1]);
      const char eventType = event[0][0];
      return pair<int, char>{timestamp, -eventType};
    });

    for (const vector<string>& event : events) {
      const string eventType = event[0];
      const int timestamp = stoi(event[1]);
      // Bring users back online if their offline period has ended.
      while (!offlineQueue.empty() &&
             offlineQueue.top().returnTimestamp <= timestamp)
        online[offlineQueue.top().userId] = true, offlineQueue.pop();
      if (eventType == "MESSAGE") {
        const string mentionsString = event[2];
        if (mentionsString == "ALL") {
          ++allMentionsCount;
        } else if (mentionsString == "HERE") {
          for (int userId = 0; userId < numberOfUsers; ++userId)
            if (online[userId])
              ++ans[userId];
        } else {
          for (const int userId : getUserIds(mentionsString))
            ++ans[userId];
        }
      } else if (eventType == "OFFLINE") {
        const int userId = stoi(event[2]);
        online[userId] = false;
        // Add to queue to bring back online after 60 units.
        offlineQueue.emplace(timestamp + 60, userId);
      }
    }

    // Add the "ALL" mentions to all users.
    for (int userId = 0; userId < numberOfUsers; ++userId)
      ans[userId] += allMentionsCount;
    return ans;
  }

 private:
  vector<int> getUserIds(const string& s) {
    vector<int> integers;
    istringstream iss(s);
    for (string id; iss >> id;)
      integers.push_back(stoi(id.substr(2)));
    return integers;
  }
};

class Solution {
  public int[] countMentions(int numberOfUsers, List<List<String>> events) {
    record OfflineUser(int returnTimestamp, int userId) {}
    int[] ans = new int[numberOfUsers];
    boolean[] online = new boolean[numberOfUsers];
    Arrays.fill(online, true);
    // min-heap to track users that are offline
    Queue<OfflineUser> offlineQueue =
        new PriorityQueue<>(Comparator.comparingInt(OfflineUser::returnTimestamp));
    int allMentionsCount = 0;

    events.sort(
        Comparator.comparingInt((List<String> event) -> Integer.parseInt(event.get(1)))
            .thenComparing((List<String> event) -> event.get(0), Comparator.reverseOrder()));

    for (List<String> event : events) {
      final String eventType = event.get(0);
      final int timestamp = Integer.parseInt(event.get(1));
      // Bring users back online if their offline period has ended.
      while (!offlineQueue.isEmpty() && offlineQueue.peek().returnTimestamp <= timestamp)
        online[offlineQueue.poll().userId] = true;
      if (eventType.equals("MESSAGE")) {
        String mentionsString = event.get(2);
        if (mentionsString.equals("ALL")) {
          ++allMentionsCount;
        } else if (mentionsString.equals("HERE")) {
          for (int userId = 0; userId < numberOfUsers; ++userId)
            if (online[userId])
              ++ans[userId];
        } else {
          for (final int userId : getUserIds(mentionsString))
            ++ans[userId];
        }
      } else if (eventType.equals("OFFLINE")) {
        final int userId = Integer.parseInt(event.get(2));
        online[userId] = false;
        // Add to queue to bring back online after 60 units
        offlineQueue.offer(new OfflineUser(timestamp + 60, userId));
      }
    }

    // Add the "ALL" mentions to all users.
    for (int userId = 0; userId < numberOfUsers; ++userId)
      ans[userId] += allMentionsCount;

    return ans;
  }

  private List<Integer> getUserIds(final String s) {
    List<Integer> integers = new ArrayList<>();
    for (String part : s.split(" "))
      integers.add(Integer.parseInt(part.substring(2)));
    return integers;
  }
}

from dataclasses import dataclass


@dataclass(frozen=True)
class OfflineUser:
  returnTimestamp: int
  userId: int

  def __lt__(self, other):
    return self.returnTimestamp < other.returnTimestamp


class Solution:
  def countMentions(
      self,
      numberOfUsers: int,
      events: list[list[str]]
  ) -> list[int]:
    ans = [0] * numberOfUsers
    online = [True] * numberOfUsers
    offlineQueue = []  # min-heap to track users that are offline
    allMentionsCount = 0

    events.sort(key=lambda x: (int(x[1]), -ord(x[0][0])))

    for eventType, t, messageContent in events:
      timestamp = int(t)
      # Bring users back online if their offline period has ended.
      while offlineQueue and offlineQueue[0].returnTimestamp <= timestamp:
        user = heapq.heappop(offlineQueue)
        online[user.userId] = True
      if eventType == "MESSAGE":
        match messageContent:
          case "ALL":
            allMentionsCount += 1
          case "HERE":
            for userId in range(numberOfUsers):
              if online[userId]:
                ans[userId] += 1
          case _:
            for userId in [int(part[2:]) for part in messageContent.split()]:
              ans[userId] += 1
      elif eventType == "OFFLINE":
        userId = int(messageContent)
        online[userId] = False
        # Add to queue to bring back online after 60 units.
        heapq.heappush(offlineQueue, OfflineUser(timestamp + 60, userId))

    # Add the "ALL" mentions to all users.
    for userId in range(numberOfUsers):
      ans[userId] += allMentionsCount
    return ans