253. Meeting Rooms II

The idea is to sort the intervals first according to the start time. Then set up a minimum heap according the end time. So when we take the top interval of the heap, we'll get the meeting that ends up earliest. If the new interval starts behind the top meeting, we can reuse the meeting room the top one was using so we don't have to order a new meeting room. All we need to do is to update the end time of this room to eh new interval's end time. Why we don't need to care the gap between the last meeting and the new meeting? Because the intervals are sorted by start time, so it's guaranteed that no new meeting will insert into the gap.

1:  /**  
2:   * Definition for an interval.  
3:   * struct Interval {  
4:   *   int start;  
5:   *   int end;  
6:   *   Interval() : start(0), end(0) {}  
7:   *   Interval(int s, int e) : start(s), end(e) {}  
8:   * };  
9:   */  
10:  struct compare {  
11:    bool operator() (const Interval& a, const Interval& b){  
12:      return a.end > b.end;  
13:    }  
14:  };  
15:  class Solution {  
16:  public:  
17:    int minMeetingRooms(vector<Interval>& intervals) {  
18:      if (intervals.size() == 0) return 0;  
19:      // sort according to the start time.  
20:      sort(intervals.begin(), intervals.end(), [](Interval a, Interval b) { return a.start < b.start; });  
21:      priority_queue<Interval, vector<Interval>, compare> min_heap;  
22:      min_heap.push(intervals[0]);  
23:      for (int i = 1; i < intervals.size(); i++) {  
24:        Interval interval = min_heap.top();  
25:        min_heap.pop();  
26:        if (interval.end > intervals[i].start) {  
27:          min_heap.push(intervals[i]);  
28:        } else {  
29:          interval.end = intervals[i].end;  
30:        }  
31:        min_heap.push(interval);  
32:      }  
33:      return min_heap.size();  
34:    }  
35:  };  

When I revisited this problem, I had a more concise solution with the same idea behind. I don't have to store the intervals in the min heap but the ending time.

1:  /**  
2:   * Definition for an interval.  
3:   * struct Interval {  
4:   *   int start;  
5:   *   int end;  
6:   *   Interval() : start(0), end(0) {}  
7:   *   Interval(int s, int e) : start(s), end(e) {}  
8:   * };  
9:   */  
10:  class Solution {  
11:  public:  
12:    int minMeetingRooms(vector<Interval>& intervals) {  
13:      if (intervals.size() < 2) return intervals.size();  
14:      sort(intervals.begin(), intervals.end(), [](Interval a, Interval b){ return a.start < b.start; });  
15:      priority_queue<int, vector<int>, greater<int>> q;  
16:      for (int i = 0; i < intervals.size(); i++) {  
17:        if (q.empty() || intervals[i].start < q.top()) q.push(intervals[i].end);  
18:        else {  
19:          int t = q.top();  
20:          q.pop();  
21:          t = intervals[i].end;  
22:          q.push(t);  
23:        }  
24:      }  
25:      return q.size();  
26:    }  
27:  };  

295. Find Median from Data Stream

I followed the top rated solution. The idea is brilliant. It keeps two heaps. One heap keeps the smaller half array and the other keep the larger half array, i.e. all the numbers in small heap is less than or equal to the ones in large heap. And we always keep small heap size is larger than or equal to the large heap size. Given that, the median will be the small heap top if small heap size is larger than the large heap size OR the average of small heap top and large heap top.

1:  class MedianFinder {  
2:  private:  
3:    priority_queue<int> small;  
4:    priority_queue<int, vector<int>, greater<int>> large;  
5:  public:  
6:    // Adds a number into the data structure.  
7:    void addNum(int num) {  
8:      if (small.empty()) { small.push(num); return; }  
9:      if (small.size() > large.size()) {  
10:        small.push(num);  
11:        large.push(small.top());  
12:        small.pop();  
13:      } else {  
14:        if (small.top() >= num) {  
15:          small.push(num);  
16:        } else {  
17:          large.push(num);  
18:          small.push(large.top());  
19:          large.pop();  
20:        }  
21:      }  
22:    }  
23:    // Returns the median of current data stream  
24:    double findMedian() {  
25:      if (small.size() == large.size()) return (small.top()+large.top())/2.0;  
26:      else return small.top();  
27:    }  
28:  };  
29:  // Your MedianFinder object will be instantiated and called as such:  
30:  // MedianFinder mf;  
31:  // mf.addNum(1);  
32:  // mf.findMedian();  

218. The Skyline Problem

I followed one of the top ranked algorithm. You can think the problem in the way that we are constructing buildings from left to right, if there are multiple buildings that we need to construct at the same point, we only need to build the highest one because this one will block the lower ones. With this idea in mind, we need a heap to track all the buildings under construction and the heap is sorted by the height of buildings. When we encounter a new building, first of all, we need to know if the buildings higher than it needs to be completed.

Case 1: the new building is away from the current highest building, then we need to pop out all the buildings that is ended before or right on the same point the highest building ends because these buildings will be blocked by the highest building. Once we are finished with removing these building in the heap, the top in the heap will be the highest building that ends behind and our point will be drawn at this point, i.e. <end point of last top building, height of the current top building>. Note, if current top building has the same height of last top one, we don’t have to push the point to the result because the new top building is connected with the last top building.

Case 2: if the new building is overlapping with the top building, we need to push the new building to the heap and move to next building. Particularly, we need to push all the new buildings starting at the same point into the heap. And then we’ll see if we can push the new building’s starting point into result. The only case will be that the new building’s height is larger than the current top one. Note we have pushed the new building to the heap and the top will be the new building itself. Then the question is how to get the highest building before the new one? Here is the trick, the result itself caches the height too! The end of the result will be the highest building before the new building. So we can compare the last building in the result with the current building. If the top height is larger than the last one, push the starting point of the new building into result.

When I revisited this problem, I made mistakes in
line 7: I was doing "for (i = 0; i < buildings.size(); i++)". This is wrong because even if i == buildings.size(), it's still possible that live heap isn't empty. Therefore, we still need to process the live buildings in the heap until the heap becomes empty.
line 9, 12: This is the case where I need to process the buildings in the heap. So I need to include the case of "i == n". Also, note that x at this moment is the ending point of the highest building in the heap
line 15-18: I need to include overlapping buildings into the heap so that we only output the left point of the highest point starting from the same point. Otherwise, for case "[[1,2,1],[1,2,2],[1,2,3]]", the output will be "[[1,1],[1,2],[1,3],[2,0]]".
line 26: Minor mistake but easy to make.

1:  class Solution {  
2:  public:  
3:    vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {  
4:      vector<pair<int, int>> res;  
5:      priority_queue<pair<int, int>> live;  
6:      int i = 0, n = buildings.size();  
7:      while (i < n || !live.empty()) {  
8:        int x = live.empty() ? buildings[i][0] : live.top().second;  
9:        if (i == n || buildings[i][0] > x) {  
10:          // pop out all the buildings that ends before the highest one.  
11:          // and the x position is where the highest building ends.  
12:          while (!live.empty() && live.top().second <= x) live.pop();  
13:        } else {  
14:          x = buildings[i][0];  
15:          while (i < n && buildings[i][0] == x) {  
16:            live.push(make_pair(buildings[i][2], buildings[i][1]));  
17:            i++;  
18:          }  
19:        }  
20:        // Now the x position is the highest building so far  
21:        int h = live.empty() ? 0 : live.top().first;  
22:        // In case1, the new point will have previously highest building's ending x position  
23:        // and the current highest building's height.  
24:        // In case2, the x position will be the current building's position. However, if  
25:        // the current building is not the highest, it will not be pushed into the result.  
26:        if (res.empty() || res.back().second != h) res.push_back(make_pair(x, h));  
27:      }  
28:      return res;  
29:    }  
30:  };  

355. Design Twitter

We need to use hash map to store the mapping between one follower and followees. Each follower has multiple followees so we need set to store all followees for one follower. For tweets, we need to add timeline for each tweet such that we know which is the latest one. When popping out top latest 10 tweets of a user, all we need to do is:
(1). Get all friends of this user.
(2). Iterate the friend list.
(3). For each friend, iterate his/her tweets list.
(4). We use a priority queue with least recent tweets on top to keep the 10 most recent tweets. If the queue is not full, we keep pushing. If the queue is full, we check the top tweet is less recent than the incoming tweet. If so, push the incoming tweet into the queue. If not, we stop scanning this friend's tweets because his/her tweets are ordered from most recent to least recent. If the queue size is large than 10, we pop out the top.
(5). At the end, we output tweets in the queue in reverse order.

Also, one important point that can be easy to miss is that user herself need to follow herself! Why? Because she must be able to see her own tweets. Also when doing unfollow, we need to make sure that user mustn't unfollow herself.

Note, line 14 is an optimization for getNewsFeed(), so that line 22 can detect early break.

1:  class Twitter {  
2:  private:  
3:    unordered_map<int, unordered_set<int>> friends;  
4:    unordered_map<int, vector<pair<int, int>>> tweets;  
5:    int time;  
6:  public:  
7:    /** Initialize your data structure here. */  
8:    Twitter() {  
9:      time = 0;  
10:    }  
11:    /** Compose a new tweet. */  
12:    void postTweet(int userId, int tweetId) {  
13:      follow(userId, userId);  
14:      tweets[userId].insert(tweets[userId].begin(), pair<int, int>(++time, tweetId));  
15:    }  
16:    /** Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent. */  
17:    vector<int> getNewsFeed(int userId) {  
18:      vector<int> res;  
19:      priority_queue<pair<int, int>, vector<pair<int, int>>, std::greater<pair<int, int>>> que;  
20:      for (int f : friends[userId]) {  
21:        for (pair<int, int> t : tweets[f]) {  
22:          if (que.size() == 10 && que.top().first > t.first) break;  
23:          que.push(t);  
24:          if (que.size() > 10) que.pop();  
25:        }  
26:      }  
27:      while (!que.empty()) {  
28:        res.push_back(que.top().second);  
29:        que.pop();  
30:      }  
31:      reverse(res.begin(), res.end());  
32:      return res;  
33:    }  
34:    /** Follower follows a followee. If the operation is invalid, it should be a no-op. */  
35:    void follow(int followerId, int followeeId) {  
36:      friends[followerId].insert(followeeId);  
37:    }  
38:    /** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */  
39:    void unfollow(int followerId, int followeeId) {  
40:      if (followerId != followeeId) {  
41:        friends[followerId].erase(followeeId);  
42:      }  
43:    }  
44:  };  
45:  /**  
46:   * Your Twitter object will be instantiated and called as such:  
47:   * Twitter obj = new Twitter();  
48:   * obj.postTweet(userId,tweetId);  
49:   * vector<int> param_2 = obj.getNewsFeed(userId);  
50:   * obj.follow(followerId,followeeId);  
51:   * obj.unfollow(followerId,followeeId);  
52:   */