Troubles understanding this Interval Scheduling question

Question

Can someone explain how to prove what this question is asking? I'm terrible at proofs and the fact that I don't even understand the hint is very troubling. This is a homework question.

Consider the Interval Scheduling problem. We have seen that the “earliest deadline-first” greedy algorithm finds an optimal set of jobs.

Consider now the “shortest-job-first” greedy algorithm, which initially sorts the jobs by increasing duration — i.e., so that f(1)−s(1) ≤ f(2)−s(2) ≤ . . . ≤ f(n)−s(n). It then considers the jobs in this order; each job considered is added to a set A (initially empty) if it does not conflict with any job currently in A. Thus, at the end, the algorithm has produced a set of non-conflicting jobs A. (In contrast, the “earliest-finish-time-first” algorithm initially sorts the jobs by increasing finish time — i.e., so that f(1) ≤ f(2) ≤ . . . ≤ f(n). Other than the initial sorting of jobs, the two algorithms are the same.) We have seen that the “shortest-job-first” greedy algorithm does not necessarily produce an optimal set of jobs.

In this problem you must prove that it produces a set of feasible jobs whose size is at least half the size of an optimal set. Thus, in some sense, the set of jobs produced by this algorithm is not too bad compared to the optimum. (Contrast this to the “earliest-start-time-first” algorithm, which produces a set of jobs whose size can be an arbitrarily small fraction of the optimal.) More precisely, let m be the size of an optimal set of jobs, and let A be the set of jobs computed by the shortest-job first greedy algorithm. Prove that |A| ≥ m/2.

Hint. Let B be any optimal set of jobs and j be any job in A. What is the maximum number jobs in B with which j conflicts?

Answer 1

You'll want to start by answering the question in the hint, and then make another argument to obtain the final result.

The hint is saying that for any job $j \in A$, there is a fixed upper bound on the number of intervals in $B$ with which $j$ overlaps. Think about what happens if $j$ intersects with three or more intervals in $B$. Would this be possible using the Shortest-Job-First algorithm?

Let the upper bound you obtain from the hint be $k$. Then, you can make the following argument (presented informally, as it is just a hint). Using our result above, we can state that in the worst case, we have each $j \in A$ overlapping with a subset of $k$ distinct jobs of $B$, where these subsets of $k$ jobs are pairwise disjoint. This gives you an upper bound on $|B|$ in terms of $|A|$.

Can you take it from here?