CareerCup

import java.util.NavigableSet;
import java.util.TreeSet;

public class OverlappingProgram {

    static class Program {
        int startTime;
        int endTime;

        Program(int startTime, int duration){
            this.startTime = startTime;
            this.endTime = startTime + duration;
        }
    }

    static boolean isOverlapping(NavigableSet<Program> programs, Program program) {

        if (programs.isEmpty()) {
            return false;
        }

        //1. Test if ceiling is overlapping
        Program ceiling = programs.ceiling(program);
        if (ceiling != null) {
            // found ceiling - test if overlapping
            if (program.endTime > ceiling.startTime) {
                return true;
            }

            //2. Test if lower to ceiling is overlapping
            Program lower = programs.lower(ceiling);
            if (lower == null){
                return false;
            } else {
                return program.startTime < lower.endTime;
            }

        } else {// no ceiling means program.startTime > existing programs
            //test for overlapping with last element
            return program.startTime < programs.last().endTime;
        }
    }


    public static NavigableSet<Program> addPrograms(Program[] inputPrograms) {
        NavigableSet programs = new TreeSet<Program>((o1, o2) -> o1.startTime - o2.startTime);

        for (Program program : inputPrograms) {
            if (!isOverlapping(programs, program)){
                programs.add(program);
                System.out.println("Added program with start date " + program.startTime);
            } else {
                System.out.println("Overlapping program with start date " + program.startTime);
            }
        }
        return programs;
    }

    public static void main(String[] args) {
        Program p1 = new Program(10, 5);
        Program p2 = new Program(25, 15);
        Program p3 = new Program(18, 7);
        Program p4 = new Program(12, 10);

        Program[] inputPrograms = new Program[] {p1, p2, p3, p4};
        addPrograms(inputPrograms);
    }
}

bool CanProgramStarted(list<pair<int,int>> runningProgram, pair<int,int> Programs)
{
	list<pair<int, int>>::iterator itList;
	//if starting time falls b/w existing start and end time then No otherwise yes
	for (itList = runningProgram.begin() ; itList != runningProgram.end() ; itList++)
	{
		if (Programs.first >= itList->first && Programs.first <= (itList->first + itList->second))
			return false;
		
	}

	//Add the program to the list
	runningProgram.push_back(Programs);
	return true;
}


//_CRT_SECURE_NO_WARNINGS

int main()
{
	list<pair<int, int>> runningProgram;
	pair<int, int> progrm1(10, 5);
	pair<int, int> progrm2(25, 15);

	   
	runningProgram.push_back(progrm1);
	runningProgram.push_back(progrm2);

	pair<int, int> progrm3(18, 7);
	printf("Program start status : %d \r\n", CanProgramStarted(runningProgram, progrm3));

	pair<int, int> progrm4(12, 10);
	printf("Program start status : %d \r\n", CanProgramStarted(runningProgram, progrm4));

}

Are scheduled programs always sorted in ascending order of their start times?

There are two ways to solve this:
The first approach is naive: use hash to mark all busy points in time. Whenever we want to check if a program can be added, we simply loop over its range (start -> start + duration) and checking if any of the points is already marked in the hash. The complexity is O(k) where k is the duration. One problem (major one): if a program is set to work indefinitely , the performance is poor :)

A better approach:
use set (ordered set, insert is o(log n), then use binary search to find the first elements that starts *after* the program that we want to add starting point and check if this program or the one before it (if any) are conflicting

The complexity: is o(log n) - where n is the number programs we have in the set

#include <iostream>
#include <set>
#include <sstream>
#include <stdio.h>

using namespace std;

struct Program {
    int start = -1;
    int duration = -1;
    int GetDuration() const { return duration; }
    int GetStartTime() const { return start; }
    int GetEndTime() const { return start + duration; }
    bool InRange(int t, bool checkingStartTime) const
    {
        if(checkingStartTime) {
            // t is the start time
            return t >= GetStartTime() && t < GetEndTime();
        } else {
            // t is the end time
            return t > GetStartTime() && t < GetEndTime();
        }
    }
    bool Conflicts(const Program& p) const
    {
        return InRange(p.GetStartTime(),
                   true) || // The starting point of P is conflicting with the exeuction of this program
            InRange(p.GetEndTime(), false) || // The ending point of P is conflicting with the exeuction of this program
            (p.GetStartTime() <= GetStartTime() &&
                p.GetEndTime() >=
                    GetEndTime()); // P execution time starts before this program and ends after (i.e p contains this)
    }
    // Required by std::set
    bool operator<(const Program& p) const { return GetStartTime() < p.GetStartTime(); }
    std::string ToString() const
    {
        std::stringstream ss;
        ss << "[" << GetStartTime() << ", " << GetDuration() << "]";
        return ss.str();
    }
};

bool AddIfPossible(const Program& p, set<Program>& T)
{
    // empty T? just add the program
    if(T.empty()) {
        T.insert(p);
        return true;
    }

    // end should point to the first element that its starting time is greater than or p.GetStartTime()
    auto end = T.lower_bound(p);
    // No program that start after this one?
    if(end == T.end()) {
        // get the last element and check if it conflicts with p
        auto it = T.rbegin();
        if(!it->Conflicts(p)) {
            T.insert(p);
            return true;
        } else {
            cout << "Program: " << p.ToString() << " conflicts with " << it->ToString() << endl;
        }
    } else {
        // end starts after p
        auto start = T.end();
        if(end != T.begin()) { start = --end; }

        if(!end->Conflicts(p) && (start != T.end() && !start->Conflicts(p))) {
            T.insert(p);
            return true;
        } else if(end->Conflicts(p)) {
            cout << "Program: " << p.ToString() << " conflicts with " << end->ToString() << endl;
        } else if(start != T.end()) {
            cout << "Program: " << p.ToString() << " conflicts with " << start->ToString() << endl;
        }
    }
    return false;
}

int main(int argc, char** argv)
{
    Program P1{ 10, 5 };
    Program P2{ 25, 15 };
    Program P3{ 18, 7 };
    Program P4{ 12, 10 };
    Program P5{ 28, 2 };
    
    set<Program> T;
    AddIfPossible(P1, T);
    AddIfPossible(P2, T);
    AddIfPossible(P3, T);
    AddIfPossible(P4, T);
    AddIfPossible(P5, T);

    return 0;
}

Approach: If the new program falls into the already scheduled program duration or if the duration range of the new program is greater and falls into the already scheduled program then we cannot schedule the new program. Else we can schedule.

I wrote the below code to the interviewer and said that the time complexity is O(n) where n is the number of new programs or scheduled programs.
He asked me to check for any other occurrences of overlappings and also asked me to reduce the time complexity. I said that we can use binary search by ordering the scheduled programs based on their startTimes and the time complexity would be O(logn). The interviewer is satisfied with O(logn) time complexity.

int[][] scheduledPrograms = { {10,5}, {25, 15} };
int[][] newPrograms = { {18,7}, {12, 10} };

public void processNewPrograms(int[][] newPrograms, int[][] scheduledPrograms) {
	for(int i=0; i< newPrograms.length; i++) {
        	int startTime = newPrograms[i][0];
			int endTime = newPrograms[i][0] + newPrograms[i][1];
			System.out.println(" Whether the Program-" + (i+1) + " can be scheduled: "+canProgramSchedule(startTime, endTime, scheduledPrograms);
                
    }
}

public boolean canProgramSchedule(int startTime, int endTime, int[][] scheduledPrograms) {
	for(int i=0; i< scheduledPrograms.length; i++) {
		int scheduledStartTime = scheduledPrograms[i][0];
		int scheduledEndTime = scheduledPrograms[i][0] + scheduledPrograms[i][1];
		// To check the new Program falls into the already scheduled Program duration.
		if( (startTime >= scheduledStartTime && startTime < scheduledEndTime) || (endTime >= scheduledStartTime && endTime < scheduledEndTime) ) {
			return false;
		} 
		//I forgot to tell below if condition to the interviewer. Later I realized and adding here now. Are there any other overlappings?
		//To check any overlapping if the duration range of new program is greater than the already scheduled programs
		else if( (scheduledStartTime >= startTime && scheduledStartTime < endTime) || (scheduledEndTime >= startTime && scheduledEndTime < endTime) ) {
		    return false;
		}
	}
	return true;
}

If the first newProgram (for eg., P3) can be sheduled then add it to the sheduledPrograms array and then process for P4. I didn't cover this scenario in my above coding.
Then we can return true, false for {18,7}, {20,2}.

In order to schedule a new process, we need to check if there is any overlap with the existing processes.
This means a new process:
Can NOT start before the previous process is finished running.
Can NOT end after the next process starts running.

I believe this algorithm runs in O(N log N).
N processes with insertion/lookup occurring in log N time.

package sandbox;

import java.util.NavigableSet;
import java.util.TreeSet;

// Needs to implement Comparable for NavigableSet.
class Process implements Comparable<Process> {
	public Process() {

	}

	public Process(int s, int r) {
		startTime = s;
		runTime = r;
		endTime = s + r;
	}

	public int getStartTime() {
		return startTime;
	}

	public int getRunTime() {
		return runTime;
	}

	public int getEndTime() {
		return endTime;
	}

	@Override
	public int compareTo(Process p) {
		return this.startTime - p.getStartTime();
	}

	private int startTime = 0;
	private int runTime = 0;
	private int endTime = 0;
}

public class Sandbox {

	public static void main(String[] args) {
		NavigableSet<Process> set = new TreeSet<>();
		addProcess(set, new Process(10, 5));
		addProcess(set, new Process(25, 15));
		addProcess(set, new Process(18, 7));
		addProcess(set, new Process(12, 10));
		printSet(set);
	}

	public static boolean addProcess(NavigableSet<Process> s, Process p) {
		if (s.isEmpty()) {
			s.add(p);
			return true;
		}
		Process prevProcess = s.floor(p);
		if (prevProcess.getEndTime() > p.getStartTime()) { // Previous process ends after new one starts
			return false;
		}
		Process nextProcess = s.ceiling(p);
		if (nextProcess != null) {
			if (nextProcess.getStartTime() < p.getEndTime()) { // Next process starts before new one ends
				return false;
			}
		}
		s.add(p);
		return true;
	}

	public static void printSet(NavigableSet<Process> s) {
		System.out.print("Set contains: ");
		for (Process p : s) {
			System.out.print("[" + p.getStartTime() + "|" + p.getRunTime() + "]");
			if (!p.equals(s.last())) {
				System.out.print(", ");
			}
		}
	}

}

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<stdbool.h>


int processArr[50] = {10,5,25,15};

void insertprocess(int startT, int executionT)
{
     int i=0 , j= 0;

    while(processArr[i])
    {
        if(startT<(processArr[i]+processArr[i+1])||(startT+executionT)>processArr[i+2])
        {
            printf("The process can't be added");
        }
        else 
        {
           while(processArr[j])
            {
                j++;
            }
            processArr[j] = startT;
            processArr[j+1] = executionT; 
        }
        i = i+2;
    }
}

int main()
{
    int i=0, j=0;

    insertprocess(16,10);

    while(processArr[i])
    {
        printf("\n%d\n",processArr[i]);
        i++;
    }
    return 0;
}

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<stdbool.h>


int processArr[50] = {10,5,25,15};

void insertprocess(int startT, int executionT)
{
     int i=0 , j= 0;

    while(processArr[i])
    {
        if(startT<(processArr[i]+processArr[i+1])||(startT+executionT)>processArr[i+2])
        {
            printf("The process can't be added");
        }
        else 
        {
           while(processArr[j])
            {
                j++;
            }
            processArr[j] = startT;
            processArr[j+1] = executionT; 
        }
        i = i+2;
    }
}

int main()
{
    int i=0, j=0;

    insertprocess(16,10);

    while(processArr[i])
    {
        printf("\n%d\n",processArr[i]);
        i++;
    }
    return 0;

}

here you go:
c lang

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<stdbool.h>


int processArr[50] = {10,5,25,15};

void insertprocess(int startT, int executionT)
{
     int i=0 , j= 0;

    while(processArr[i])
    {
        if(startT<(processArr[i]+processArr[i+1])||(startT+executionT)>processArr[i+2])
        {
            printf("The process can't be added");
        }
        else 
        {
           while(processArr[j])
            {
                j++;
            }
            processArr[j] = startT;
            processArr[j+1] = executionT; 
        }
        i = i+2;
    }
}

int main()
{
    int i=0, j=0;

    insertprocess(16,10);

    while(processArr[i])
    {
        printf("\n%d\n",processArr[i]);
        i++;
    }
    return 0;
}

here we go:
c lang

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<stdbool.h>


int processArr[50] = {10,5,25,15};

void insertprocess(int startT, int executionT)
{
     int i=0 , j= 0;

    while(processArr[i])
    {
        if(startT<(processArr[i]+processArr[i+1])||(startT+executionT)>processArr[i+2])
        {
            printf("The process can't be added");
        }
        else 
        {
           while(processArr[j])
            {
                j++;
            }
            processArr[j] = startT;
            processArr[j+1] = executionT; 
        }
        i = i+2;
    }
}

int main()
{
    int i=0, j=0;

    insertprocess(16,10);

    while(processArr[i])
    {
        printf("\n%d\n",processArr[i]);
        i++;
    }
    return 0;
}

In Scala:

import scala.collection.immutable.TreeSet

case class Program(startTime : Int, duration : Int) {
  def endTime():Int = startTime + duration
}

object OverlappingPrograms {
  def main(args: Array[String]): Unit = {
    val p1 = Program(10, 5)
    val p2 = Program(25, 15)
    val p3 = Program(18, 7)
    val p4 = Program(12, 10)
    val inputPrograms = Array(p1, p2, p3, p4)
    val set = addPrograms(inputPrograms)

    set.foreach(println)
  }

  def addPrograms(inputPrograms: Seq[Program]): TreeSet[Program] = {
    inputPrograms.foldLeft(TreeSet.empty[Program](Ordering.by(_.startTime)))((acc, x) => {
      if (!isOverlapping(acc, x)) acc + x else acc
    })
  }

  def isOverlapping(programs: TreeSet[Program], program: Program): Boolean = {
    if (programs.isEmpty) {
      false
    } else {
      val ceiling = programs.from(program)
      if (ceiling.nonEmpty) {
        val nextProgram = ceiling.head
        if (program.endTime > nextProgram.startTime) {
          true
        } else {
          val lower = programs.to(nextProgram)
          lower.nonEmpty && program.startTime < lower.head.endTime
        }
      } else {
        program.startTime < programs.last.endTime
      }
    }
  }

}

#--Python:

import sets

class program:


def __init__(self,x,y):
self.set_val = set([])

for i in range(y):
# print(i)
self.set_val.add(x+i)

print("set (" + str(x) +"," +str(y) + "): " + str(sorted(self.set_val)))


def main2():

p1=program(10,5)
p2=program(25,15)
p3=program(18,7)
p4=program(12,10)


if(p1.set_val.isdisjoint(p4.set_val) and p2.set_val.isdisjoint(p4.set_val)):
print("P4 can be added")
else:
print("P4 can NOT be added")

if(p1.set_val.isdisjoint(p3.set_val) and p2.set_val.isdisjoint(p3.set_val)):
print("P3 can be added")
else:
print("P3 can NOT be added")


main2()

bool CanProgramStarted(list<pair<int,int>> runningProgram, pair<int,int> Programs)
{
	list<pair<int, int>>::iterator itList;
	//if starting time falls b/w existing start and end time then No otherwise yes
	for (itList = runningProgram.begin() ; itList != runningProgram.end() ; itList++)
	{
		if (Programs.first >= itList->first && Programs.first <= (itList->first + itList->second))
			return false;
		
	}

	//Add the program to the list
	runningProgram.push_back(Programs);
	return true;
}


//_CRT_SECURE_NO_WARNINGS

int main()
{
	list<pair<int, int>> runningProgram;
	pair<int, int> progrm1(10, 5);
	pair<int, int> progrm2(25, 15);

	   
	runningProgram.push_back(progrm1);
	runningProgram.push_back(progrm2);

	pair<int, int> progrm3(18, 7);
	printf("Program start status : %d \r\n", CanProgramStarted(runningProgram, progrm3));

	pair<int, int> progrm4(12, 10);
	printf("Program start status : %d \r\n", CanProgramStarted(runningProgram, progrm4));

}

ata Time = Time Int Int Time Time |
  Empty deriving Show

insertInterval :: (Int, Int) -> Time -> Time
insertInterval (x, y) Empty = Time x y Empty Empty
insertInterval (x, y) (Time a b tL tR)
  | y <= a = Time a b (insertInterval (x, y) tL) tR
  | b <= x = Time a b tL (insertInterval (x, y) tR)
  | otherwise = Time a b tL tR

#include <iostream>
#include <list>
#include <algorithm>

class ProgramSchedule{
    std::list<int> *mProgSchedule = NULL;

public:
    ProgramSchedule();
    ~ProgramSchedule();
    bool CheckAndAddProgToSchedule(int s, int e);
    void RunTest(void);
    void DisplayProgSchedule(void);
};

ProgramSchedule::ProgramSchedule(){
    mProgSchedule = new std::list<int>;
}

ProgramSchedule::~ProgramSchedule(){
    mProgSchedule->clear();
    delete mProgSchedule;
    mProgSchedule = nullptr;    
}

bool ProgramSchedule::CheckAndAddProgToSchedule(int s, int e){
    if(e<=0 || (s==0 && e==0)) return false;
    bool bRet = true;
    for (int i = s; i < s+e; i++){
        if (binary_search(mProgSchedule->begin(), mProgSchedule->end(), i)){
            bRet = false;
            break;
        }
    }
    if (bRet){
        mProgSchedule->push_back(s);
        mProgSchedule->push_back(s+e);
        mProgSchedule->sort(); //TODO - Insert s, e at exact location to avoid sort
        std::cout << "Prog Scheduled = "<< s << " " << (s+e)  << std::endl;       
    }
    else std::cout << "Prog Not Scheduled = "<< s << " " << (s+e)  << std::endl;
    return bRet;    
}

void ProgramSchedule::DisplayProgSchedule(){
    std::list<int>::iterator it;
    for (it = mProgSchedule->begin(); it != mProgSchedule->end(); it++)
        std::cout <<*it << " ";
    std::cout << std::endl;
    std::cout << std::endl;    
}

void ProgramSchedule::RunTest(void){
    CheckAndAddProgToSchedule(10, 5);
    CheckAndAddProgToSchedule(25, 15);
    CheckAndAddProgToSchedule(18, 8);
    CheckAndAddProgToSchedule(18, 7);
    CheckAndAddProgToSchedule(0, 5);
    CheckAndAddProgToSchedule(5, 10);
    CheckAndAddProgToSchedule(40, 10);
    CheckAndAddProgToSchedule(0, 50);
    CheckAndAddProgToSchedule(0, 0);
    CheckAndAddProgToSchedule(0, -1);
    CheckAndAddProgToSchedule(22, 0);
    DisplayProgSchedule();
}

int main() {
    ProgramSchedule *pP = new ProgramSchedule(); 
    pP->RunTest();
    return 0; 
}
/*
Prog Scheduled = 10 15
Prog Scheduled = 25 40
Prog Not Scheduled = 18 26
Prog Scheduled = 18 25
Prog Scheduled = 0 5
Prog Not Scheduled = 5 15
Prog Not Scheduled = 40 50
Prog Not Scheduled = 0 50
0 5 10 15 18 25 25 40
*/