Given two lists indicating friend acceptance date and the friendship removal dates:

accept = [(user1, user2, '2019-01-01'), (user1, user6, '2018-10-09'), (user3, user4, '2018-12-27'), (user1, user2, '2020-06-08')]

remove = [(user3, user4, '2019-04-07'), (user2, user1, '2020-01-01'), (user1, user6, '2020-10-09')]

**Please output **all the friend pairs with its start date and end dates, for example: [(user1, user2, '2019-01-01'，'2020-01-01'), (user1, user6, '2018-10-09', '2020-10-09'), (user3, user4, '2018-12-27', '2019-04-07'), (user1, user2, '2020-06-08', 'now')]

• The order of (user1, user2) doesn't matter in your output, but you may have (user1, user2) or (user2, user1) in the accept list or remove list
• I figure out two ways to do that
  • loop O(n^2)
  • merge two list, sort the date O(n logn)

Could someone figure out other solutions to this problem? It would be great if the code is also attached! Thanks!!