Merge Message Context Windows

You are given a chat history where each message has a unique integer id and a string content. Message IDs are strictly increasing, and the full history is ordered by id in ascending order.

A message is represented by the following read-only model:

class Message {
    int id;
    String content;
}

You are also provided with an API:

class Chat {
    /**
     * Returns the message with the given id, along with up to `windowSize`
     * messages before it and up to `windowSize` messages after it.
     *
     * The returned list is sorted by message id in ascending order.
     * If the given id does not exist, an empty list is returned.
     */
    public List<Message> getChatMessages(int id, int windowSize);
}

Implement the ChatMessageMerger class, which has the following constructor and method:

class ChatMessageMerger {
    ChatMessageMerger(Chat chat, int windowSize)
    List<Message> mergeMessages(List<Integer> ids)
}

Requirements for mergeMessages(ids):

• For each input message ID, query its context window using getChatMessages(id, windowSize).
• Merge all returned messages into a single result.
• Remove duplicates, as different context windows may overlap.
• Return the final list sorted by message id in ascending order.
• If an input ID does not exist, its query contributes nothing.

Performance requirement:

• Let M be the total number of messages returned across all API calls before deduplication.
• Your algorithm must run in strictly better time than O(M log M).

Design and implement an efficient solution.