leetcode

0 class Twitter {

1 vector<pair<int, int>> posts[501];

2 bool following[501][501] = {0};

3 int time = 0;

4

5 public:

6 Twitter() {

7 for (int i = 0; i <= 500; i++) {

8 following[i][i] = true;

9 }

10 }

11

12 void postTweet(int userId, int tweetId) { posts[userId].emplace_back(time++, tweetId); }

13

14 vector<int> getNewsFeed(int userId) {

15 using type_t = tuple<int, int, int>;

16 static const auto cmp = [](const type_t &a, const type_t &b) { return get<0>(a) < get<0>(b); };

17 priority_queue<type_t, vector<type_t>, decltype(cmp)> pq(cmp);

18

19 for (int i = 0; i <= 500; i++) {

20 if (!following[userId][i]) continue;

21

22 const int n = size(posts[i]);

23 if (n == 0) continue;

24

25 pq.emplace(posts[i][n - 1].first, i, n - 1);

26 if (size(pq) > 10) pq.pop();

27 }

28

29 vector<int> res;

30 while (!pq.empty() && size(res) < 10) {

31 const auto [time, user, idx] = pq.top();

32 pq.pop();

33 res.push_back(posts[user][idx].second);

34 if (idx - 1 >= 0) pq.emplace(posts[user][idx - 1].first, user, idx - 1);

35 }

36

37 return res;

38 }

39

40 void follow(int followerId, int followeeId) { following[followerId][followeeId] = true; }

41

42 void unfollow(int followerId, int followeeId) { following[followerId][followeeId] = false; }

43 };