ETU ACM Java Kursu: 5. Hafta (Interval Scheduling)

Bugünki dersde, sınıfları işledik ve egzersiz olarak Interval Scheduling Problem'ini çözdük.

Interval.java

public class Interval {
 
 public int beg;
 public int end;
 
 public Interval(int a, int b) {
  if (a > b) 
   throw new IllegalArgumentException();
  
  beg = a;
  end = b;
 }
 
 public int len() {
  return end - beg;
 }
 
 public boolean overlaps(Interval other) {
  return this.beg < other.end && other.beg < this.end; 
 }
 
 public String toString() {
  return "(" + beg + ", " + end + ")";
 }

}

Scheduler.java

public class Scheduler {
 
 public Interval[] request;
 
 public Scheduler(Interval[] arr) {
  request = arr;
 }
 
 private Interval firstEnding() {
  Interval firstEnding = request[0];
  for (int i = 0; i < request.length; i++) {
   if (request[i].end < firstEnding.end) 
    firstEnding = request[i];
  }
  return firstEnding;
 }
 
 private void remove(Interval removing) {
  Interval[] update = new Interval[request.length - 1]; 
  for (int i = 0, j = 0; i < request.length; i++, j++) {
   if (request[i] != removing)
    update[j] = request[i];
   else
    j--;
  }
  request = update;
 }
 
 private void removeOverlapsWith(Interval interval) {
  for (int i = 0; i < request.length; i++) {
   if (request[i].overlaps(interval)) {
    remove(request[i]);
    i--;
   }
  }
 }
  
 public void schedule() {
  while (request.length != 0) {
   System.out.println(firstEnding());
   removeOverlapsWith(firstEnding());
  } 
 }
 
 public static void main(String[] args) {
  Interval[] reqs = { new Interval(3, 8),
       new Interval(9, 16),
       new Interval(13, 18),
       new Interval(20, 32),
       new Interval(26, 30)};
  
  new Scheduler(reqs).schedule();; 
 }
}

Ayrıca isteyenler için, küçük bir ödev vermiştim: firstEnding'i her defasında bütün arrayi dolanarak, tekrar tekrar bulmak yerine; array'i başlangıçta end'e göre küçükten büyüğe sıralayarak programı hızlandırın. Array'i başlangıçta interval'ların end'ine göre sıralarsak, end'i en küçük olan Interval array'in ilk elamanı olacaktır. Böylece firstEnding methodunda, tüm arrayi taramak yerine array'in sadece ilk elamanını dönmek yeterli olacaktır.