the interval scheduling problem and proved that the algorithm described (choosin

Question

the interval scheduling problem and proved that the algorithm described (choosing the interval with earliest deadline) below, always finds an optimal solution. For this problem you will write, analyze, and test several implementations of this algorithm.

The following scheduling problem. Imagine you are a highly-in- demand actor, who has been presented with offers to star in n different movie projects under development. Each offer comes specified with the first and last day of filming. To take the job, you must commit to being available throughout this entire period. Thus you cannot simultaneously accept two jobs whose intervals overlap.Must solve the following algorithmic scheduling problem:

Problem: Movie scheduling Problem
Input: A set I of n intervals on the line.
Output: What is the largest subset of the mutually non-overlapping intervals which can selected from I?

Efficient algoritm:
OptimalScheduling (I)
While (I ! = 0) d0
Accept the job from I with the earliest completion date.
Delete j, and any interval, which intersects j from I.

use a binary search tree to store the set of intervals. Use the TreeSet class below. (Remember that you can iterate over all nodes in order using an iterator returned by the iterator() method.) Again, analyze the implementation and identify a bound on the execution time. (Note that, adding, searching, and removing elements is O(log n) for TreeSet.)

TreeSet class
import java.util.AbstractSet;
import java.util.Deque;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.NoSuchElementException;

public class BSTSet<E extends Comparable<? super E>> extends AbstractSet<E>
{
protected Node root;
protected int size;

protected class Node
{
public Node left;
public Node right;
public Node parent;
public E data;

public Node(E key, Node parent)
{
this.data = key;
this.parent = parent;
}
}

@Override
public boolean contains(Object obj)
{
// This cast may cause comparator to throw ClassCastException at runtime,
// which is the expected behavior
E key = (E) obj;
return findEntry(key) != null;
}

@Override
public boolean add(E key)
{
if (root == null)
{
root = new Node(key, null);
++size;
return true;
}

Node current = root;
while (true)
{
int comp = current.data.compareTo(key);
if (comp == 0)
{
// key is already in the tree
return false;
}
else if (comp > 0)
{
if (current.left != null)
{
current = current.left;
}
else
{
current.left = new Node(key, current);
++size;
return true;
}
}
else
{
if (current.right != null)
{
current = current.right;
}
else
{
current.right = new Node(key, current);
++size;
return true;
}
}
}
}

@Override
public boolean remove(Object obj)
{
// This cast may cause comparator to throw ClassCastException at runtime,
// which is the expected behavior
E key = (E) obj;
Node n = findEntry(key);
if (n == null)
{
return false;
}
unlinkNode(n);
return true;
}
protected Node findEntry(E key)
{
Node current = root;
while (current != null)
{
int comp = current.data.compareTo(key);
if (comp == 0)
{
return current;
}
else if (comp > 0)
{
current = current.left;
}
else
{
current = current.right;
}
}
return null;
}
protected Node successor(Node n)
{
if (n == null)
{
return null;
}
else if (n.right != null)
{
// leftmost entry in right subtree
Node current = n.right;
while (current.left != null)
{
current = current.left;
}
return current;
}
else
{
// we need to go up the tree to the closest ancestor that is
// a left child; its parent must be the successor
Node current = n.parent;
Node child = n;
while (current != null && current.right == child)
{
child = current;
current = current.parent;
}
// either current is null, or child is left child of current
return current;
}
}

protected void unlinkNode(Node n)
{
if (n.left != null && n.right != null)
{
Node s = successor(n);
n.data = s.data;
n = s; // causes s to be deleted in code below
}

// n has at most one child
Node replacement = null;
if (n.left != null)
{
replacement = n.left;
}
else if (n.right != null)
{
replacement = n.right;
}

// link replacement into tree in place of node n
// (replacement may be null)
if (n.parent == null)
{
root = replacement;
}
else
{
if (n == n.parent.left)
{
n.parent.left = replacement;
}
else
{
n.parent.right = replacement;
}
}

if (replacement != null)
{
replacement.parent = n.parent;
}

--size;
}

@Override
public Iterator<E> iterator()
{
return new BSTIterator();
}

@Override
public int size()
{
return size;
}

@Override
public String toString()
{
StringBuilder sb = new StringBuilder();
toStringRec(root, sb, 0);
return sb.toString();
}

private void toStringRec(Node n, StringBuilder sb, int depth)
{
for (int i = 0; i < depth; ++i)
{
sb.append(" ");
}

if (n == null)
{
sb.append("- ");
return;
}

if (n.left != null || n.right != null)
{
sb.append("+ ");
}
else
{
sb.append("- ");
}
sb.append(n.data.toString());
sb.append(" ");
if (n.left != null || n.right != null)
{
toStringRec(n.left, sb, depth + 1);
toStringRec(n.right, sb, depth + 1);
}
}
private class BSTIterator implements Iterator<E>
{
private Node current;
private Node pending;

public BSTIterator()
{
// start out at smallest value
current = root;
if (current != null)
{
while (current.left != null)
{
current = current.left;
}
}
}
@Override
public boolean hasNext()
{
return current != null;
}
@Override
public E next()
{
if (!hasNext()) throw new NoSuchElementException();
pending = current;
current = successor(current);
return pending.data;
}
@Override
public void remove()
{
if (pending == null) throw new IllegalStateException();

if (pending.left != null && pending.right != null)
{
current = pending;
}
unlinkNode(pending);
pending = null;
}
}
private class BSTIterator2 implements Iterator<E>
{
private Deque<Node> stack = new LinkedList<Node>();
private Node pending;
public BSTIterator2()
{
// start out at smallest value
Node current = root;
while (current != null)
{
stack.push(current);
current = current.left;
}
}
@Override
public boolean hasNext()
{
return !stack.isEmpty();
}

@Override
public E next()
{
if (!hasNext()) throw new NoSuchElementException();
pending = stack.pop();
Node current = pending.right;
while (current != null)
{
stack.push(current);
current = current.left;
}
return pending.data;
}
@Override
public void remove()
{
if (pending == null) throw new IllegalStateException();

if (pending.left != null && pending.right != null)
{
if (pending.parent == null)
{
stack.clear();
stack.push(pending);
}
else
{
// clear off everything in the right subtree of pending
Node rightChild = pending.right;
while(stack.pop()!= rightChild)
{
;
}
stack.push(pending);
}
}
unlinkNode(pending);
pending = null;
}
}

}

Explanation / Answer

// Search for all intervals which contain "p", starting with the // node "n" and adding matching intervals to the list "result" public void search(IntervalNode n, Point p, List result) { // Don't search nodes that don't exist if (n == null) return; // If p is to the right of the rightmost point of any interval // in this node and all children, there won't be any matches. if (p.compareTo(n.getValue()) > 0) return; // Search left children if (n.getLeft() != null) search(IntervalNode (n.getLeft()), p, result); // Check this node if (n.getKey().contains(p)) result.add(n.getKey()); // If p is to the left of the start of this interval, // then it can't be in any child to the right. if (p.compareTo(n.getKey().getStart()) < 0) return; // Otherwise, search right children if (n.getRight() != null) search(IntervalNode (n.getRight()), p, result); } The code to search for an interval is exactly the same except for the check in the middle: // Check this node if (n.getKey().overlapsWith(i)) result.add (n.getKey());

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.