first question here, I have algorithms assignment. Generaly, I know it should be greedy algorithm, but could not work out which approach to use. Here is the problem: N sections are given, which are located on one numerical axis. Each section is described by two integers - the coordinates of the left and right ends and covers the corresponding points. All coordinates are pairwise different. K pieces should be deleted from the existing sections so that the remaining sections cover the maximum number of points in total.
Input Input data: in the first line two integers - N and K (K≤N≤100000,1≤K≤100). In each of the next N lines, two integers from the range 0..10^9 - the left and right ends of the corresponding section.
Output Output data: one integer - the maximum number of unit intervals covered by remaining sections.
Note that these sections are overlapping.
As mentioned above, I have tried different greedy approeaches (sorting by start, by end, by length), Connecting to similiar problem of non-overlapping sections, problem of choosing minimum points to cover all intervals. After stackoverflow's suggestions of duplicate questions I found out basically it is Maximum Coverage Problem, but on simple test case it gave incorrect answer, so I doubt it will pass complex test-cases.
Any hint to solution would be appriciated.