摘要：的想法就是用每次得到最小的鏈表頭的值，輸出。每個都有一個關注人列表，用儲存。用戶可以發消息，關注別人，取消關注別人。可以系統得到關注人的消息合集，這個方法必須在這個層級。因為用戶只知道自己的信息。

Merge k Sorted Lists

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists == null) return null;
        // O(k) construct heap, m*logk do iterate,  Space O(k)
        // lamda expression is super slow 99ms vs 26ms Comparator
        // PriorityQueue pq = new PriorityQueue((a,b) -> (a.val-b.val));
        PriorityQueue pq = new PriorityQueue(new Comparator(){
            @Override
            public int compare(ListNode l1, ListNode l2) {
                return l1.val - l2.val;
            }
        });
        
        for(ListNode l:lists) {
            if(l != null) pq.offer(l);
        }
        // every new list need a dummy node
        ListNode dummy = new ListNode(0);
        ListNode pre = dummy;
        while(!pq.isEmpty()){
            ListNode cur = pq.poll();
            pre.next = cur;
            if(cur.next != null) pq.offer(cur.next);
            pre = pre.next;
        }
        
        return dummy.next;
    }
}

Merge k Sorted Lists的想法就是用PriorityQueue每次得到最小的鏈表頭的值，輸出。如果next!=null,繼續放到PriorityQueue里。
Twitter 本質上就是一個消息列表，按時間順序從關注人列表里得到他們的tweets并整合顯示。
每個user都有一個關注人列表，用hashset儲存。還有一個tweets消息列表，這里按時間線就已經形成一個Sorted List.
一個user要得到最新的tweets, 首先找到關注人，把他們的tweets消息列表存到PriorityQueue里，就變成了Merge k Sorted Lists.

這里用OOD是因為更接近現實情況。twitter就是一個用戶看到關注人消息集合的媒體。
基本的entity就是消息tweets和用戶user。
tweets要體現出時間線，就要模擬linkedlist。
user用戶可以發消息，關注別人，取消關注別人。
user可以twitter系統得到關注人的消息合集，這個方法必須在twitter這個層級。因為用戶只知道自己的信息。

public class Twitter {
    private static int timestamp = 0;
    
    private Map userMap;
    
    class Tweet{
        public int id;
        public int time;
        public Tweet next;
        
        public Tweet(int id) {
            this.id = id;
            time = timestamp++;
            next = null;
        }
    }
    
    public class User{
        public int id;
        public Set followed;
        public Tweet tweet_head;
        
        public User(int id) {
            this.id = id;
            followed = new HashSet();
            follow(id);
            tweet_head = null;
        }
        
        public void follow(int id) {
            followed.add(id);
        }
        
        public void unfollow(int id){
            followed.remove(id);
        }
        
        public void post(int id){
            Tweet tweet = new Tweet(id);
            tweet.next = tweet_head;
            tweet_head = tweet;
        }
    }
    
    
    
    /** Initialize your data structure here. */
    public Twitter() {
        userMap = new HashMap();
    }
    
    /** Compose a new tweet. */
    public void postTweet(int userId, int tweetId) {
        if(!userMap.containsKey(userId)){
            User u = new User(userId);
            userMap.put(userId, u);
        }
        userMap.get(userId).post(tweetId);
    }
    
    /** 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. */
    public List getNewsFeed(int userId) {
        List news = new LinkedList<>();
        if(!userMap.containsKey(userId)){
            return news;
        }
        
        Set users = userMap.get(userId).followed;
        PriorityQueue pq = new PriorityQueue(users.size(), (a,b) -> (b.time - a.time));
        for(int u:users){
            Tweet t = userMap.get(u).tweet_head;
            if(t != null)  {
                pq.offer(t);
            }
        }
        
        int n = 0;
        while(!pq.isEmpty() && n < 10) {
            Tweet t = pq.poll();
            news.add(t.id);
            if(t.next != null) {
                pq.offer(t.next);
            }
            n++;
        }
        
        return news;
    }
    
    /** Follower follows a followee. If the operation is invalid, it should be a no-op. */
    public void follow(int followerId, int followeeId) {
        if(!userMap.containsKey(followerId)){
            User u = new User(followerId);
            userMap.put(followerId, u);
        }
        if(!userMap.containsKey(followeeId)){
            User u = new User(followeeId);
            userMap.put(followeeId, u);
        }
        userMap.get(followerId).follow(followeeId);
    }
    
    /** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
    public void unfollow(int followerId, int followeeId) {
        if(!userMap.containsKey(followerId) || followerId == followeeId){
            return;
        }
        userMap.get(followerId).unfollow(followeeId);
    }
}

/**
 * Your Twitter object will be instantiated and called as such:
 * Twitter obj = new Twitter();
 * obj.postTweet(userId,tweetId);
 * List param_2 = obj.getNewsFeed(userId);
 * obj.follow(followerId,followeeId);
 * obj.unfollow(followerId,followeeId);
 */