The video content analysis department at local startup ThereTube.com has identified certain frames f1, f2,...,fn of a long video sequence V as significant. These frames are to be archived within 5-second video clips, extracted from V at the original resolution. Once the extraction is done, V will be converted to a low-resolution, compressed format and the original discarded, making it impossible to obtain arbitrary frames at the original resolution unless they are parts of the special 5-second clips. Note: there are 24 frames per second in both the original and the clips.
The archiver's job is to determine a set {C1, C2,...,Cm} of 5-second clips (i.e., their starting frames) such that each fi is contained in at least one of the clips, and such that as few clips as possible are used. The archiver's plan is to look first for a maximal group of frames that can all be covered by one clip, capture that clip, check off the frames that have been handled, and then recursively process the rest until all the fi are covered.
(a) You've been hired as an outside consultant to evaluate the archiver's method, in part because the company is interested in automating this phase of the process. Is the archiver's method optimal? If so, give an argument for it. If not, give an example set of frames where it fails, and offer a method that is optimal and explain why it is.
Here is a diagram showing one instance of the problem, with time going left to right. The archiver has used three clips here to cover the 6 special frames.
V-------------------------------------------
f1 f2 f3 f4 f5 f6
C3------ C1------ C2------