intervals - How to prove greedy algorithm optimality -

intervals - How to prove greedy algorithm optimality -

let s set of intervals (containing n number of intervals) of natural numbers might overlap , n list of numbers (containing n number of numbers).

i want find smallest subset (let's phone call p) of s such each number in our list n, there exists @ to the lowest degree 1 interval in p contains it. intervals in p allowed overlap.

trivial example:

s = {[1..4], [2..7], [3..5], [8..15], [9..13]} n = [1, 4, 5] // p = {[1..4], [2..7]}

i found solution problem shown below

n = mergesort (n) upper, lower = infinity, -1 p = empty set each q in n if (q>=lower , q<=upper)=false max_interval = [-infinity, infinity] each r in s if q in r if r.rightendpoint > max_interval.rightendpoint max_interval = r p.append(max_interval) lower = max_interval.leftendpoint upper = max_interval.rightendpoint s.remove(max_interval)

i have found solution, not exclusively sure how prove optimality of greedy algorithm (that prove, give best result).

my question: how can prove optimality of greedy solution?

thanks in advance.

yes, algorithm reaches optimal solution. not formal proofs next arguments should convincing.

the array n sorted in ascending order , accessing elements accordingly in non-decreasing order. in other words, current element >= previous element. for each element, first check whether can accommodated in chosen interval , if not, proceed step 3, otherwise skip next element. for current element, choosing (so far un-chosen) interval in s such 'end' point big possible. makes sense because way can accommodate number of elements follow our current element. example, if current element 10, , have 2 candidate intervals [8, 12] , [9, 15], under no circumstances shall take former because know next elements have greater 10.

algorithm intervals discrete-mathematics