3
Maximize the number of pairs of overlapping intervals
source link: https://codeforces.com/blog/entry/127647
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Maximize the number of pairs of overlapping intervals
Given NN integer intervals [a,b][a,b], find the maximum number of pairs of overlapping intervals where each interval can belong to at most one pair.
Two intervals overlap if they share a common point, including closed endpoints.
The answer to the example above is 2. Pair the 2 black intervals and the 2 red intervals together.
What is the best time complexity that can be achieved for this problem? Currently I'm not sure if it's even solvable in polynomial time.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK