2.9 Learning union of intervals. Give a PAC-learning algorithm for the concept class C2 formed by unions of two closed intervals, that is [a; b][[c; d], with a; b; c; d 2 R.

Extend your result to derive a PAC-learning algorithm for the concept class Cp formed by unions of p  1 closed intervals, thus [a1; b1] [


[ [ap; bp], with ak; bk 2 R for k 2 [p]. What are the time and sample complexities of your algorithm as a function of p?