Sarnath K
BAN USERThis is a program that works with O(N). But is not always optimal. It depends on the order in which the intervals are presented to it.
I have given a good explanation below as to why this is occurring and what is the right way forward to the optimal solution.
class ScheduleFolks
{
public static class Interval {
//Assumes begin and end inclusive
public int begin;
public int end;
Interval() {
begin = end = 0;
}
Interval(int begin, int end) {
this.begin = begin;
this.end = end;
}
//Assumes ordering that this.begin <= B.begin
public int overlap(Interval B) {
if ((B.begin >= this.begin) && (B.begin <= this.end))
return (this.end - B.begin + 1);
return 0;
}
public String toString() {
return ("[" + begin + "," + end + "]");
}
}
static void findBestInterval(Interval A, Interval B, int overlaprequired, Interval C) {
Interval F = (A.begin <= B.begin) ? A : B;
Interval S = (A.begin <= B.begin) ? B : A;
int o = F.overlap(S);
if (o != 0) {
C.begin = S.begin;
C.end = S.begin + overlaprequired -1;
} else {
// We cannot do much here.
// There is no way we can make them all attend.
C.begin = F.end - overlaprequired + 1;
C.end = S.begin + overlaprequired - 1;
}
return;
}
static void findSchedulingInterval(Interval currentInterval, Interval A, int overlaprequired) {
if ((currentInterval.begin == 0) && (currentInterval.end == 0)) {
// This should not be executed in the normal case....
// But may be, only if we had only 1 interval to schedule.
currentInterval.begin = A.begin;
currentInterval.end = A.begin + overlaprequired -1;
return;
} else {
Interval F = (currentInterval.begin <= A.begin) ? currentInterval : A;
Interval S = (currentInterval.begin <= A.begin) ? A : currentInterval;
int o = F.overlap(S);
if (o != 0) {
if (o < overlaprequired) {
if (currentInterval.begin <= A.begin)
{
currentInterval.end += (overlaprequired - o);
} else {
currentInterval.begin -= (overlaprequired - o);
}
} else {
//Nothing required at this point. Don't alter the currentInterval
}
} else {
//There is no overlap at all. Simply stretch the current schedule to accomodate
if (currentInterval.begin <= A.begin) {
currentInterval.end = A.begin + overlaprequired -1;
} else {
currentInterval.begin = A.end - overlaprequired + 1;
}
}
}
return;
}
static Interval scheduleEvent(Interval[] intervals, int maxOverlap) {
Interval r = new Interval(0,0);
if (intervals.length == 1) {
findSchedulingInterval(r, intervals[0], maxOverlap);
return r;
}
//Get the first interval done manually
findBestInterval(intervals[0], intervals[1], maxOverlap, r);
for(int i=2; i<intervals.length; i++) {
System.out.println("Considering " + intervals[i] + " with current interval = " + r);
findSchedulingInterval(r, intervals[i], maxOverlap);
}
return r;
}
public static void printIntervals(Interval[] intervals) {
for(int i=0; i<intervals.length; i++) System.out.println(intervals[i]);
}
public static void main(String[] args) {
int overlaprequired = 2;
Interval[] intervals = new Interval[4];
//
//IMPORTANT NOTE
//
//Final Result is not permutation invariant
//Try the order of 0,2,1,3 while initializing below for a different final result.
//The problem arises because of the overlap betweem (1,5) and (2,10)
//The good overlap throws 3 potential intermediate candidate interval namely (2,3), (3,4) and (4,5)
//- all good while combining (1,5) and (2,10).
//For subsequent couplings, (2,3) and (4,7) turns out to be a poor choice as it stretches the window from (2 to 7)
//while (4,5) and (4,7) would have yielded us (4,5) which when coupled with (6,9) would have yielded (4,7) a the final result
//Since we go with (2,3) pair, we get (2,7) as final result.
//
//HOW TO REACH OPTIMAL SOLUTION:
//
//Sort the entries in the increasing order of interval beginning
//Whenever there are a lot of candidate solutions always optimize in favor of higher numbers
//(so that the gap between future intervals would be reduced)
//
intervals[2] = new Interval(4,7);
intervals[0] = new Interval(1, 5);
intervals[1] = new Interval(2,10);
intervals[3] = new Interval(6,9);
System.out.println("Max overlap needed = " + overlaprequired);
System.out.println("Input Intervals :");
printIntervals(intervals);
System.out.println("\nOutput Interval:");
Interval result = scheduleEvent(intervals, overlaprequired); //Change Overlap Point here
System.out.println("Result interval = [" +result.begin + ", " + result.end + " ]");
}
}
RepGinaSanchez, Computer Scientist at Autoportal.com
Ginna from New York.Successfully managing a high volume of work assignments without compromising quality to exceed client expectations.Apart ...
One idea is to represent the bit-sequence by the number of consecutive bits they have.
- Sarnath K January 25, 2017e.g.
0001111000101101 can be represented as
0-3, 1-4, 0-3, 1-1, 0-1, 1-2, 0-1, 1-1 [BALANCED]
Now you can consider the wholesum bit-sequence and start trimming the left and right sides until you reach the balance. This will the longest bitsequence you will ever get from this sequence.
For e.g. in the problem above, if you consider entire bit sequence then, you have 8 zeros and 8 ones. That is balanced already.
Now, you can shed a 0 and 1 on both sides and thus you will get your next sub-sequence which is
0-2, 1-4, 0-3, 1-1, 0-1, 1-2, 0-1 [BALANCED]
This is balanced and now you have zeros on both left and right end. Shed both of them because you cannot achieve balance by shedding them individually because you have no 1s to shed.
Shed 3 zeros and you get
1-4, 0-3, 1-1, 0-1, 1-2 [UNBALANCED by 3 zeros deficit]
and it has deficit of 3 zeros and we have shed 3 ones to achieve balance.
This can be done shedding 2 ones on the right and 1 one on the left
1-3,0-3,1-1,0-1 [BALANCED]
This is balanced.
We can again shed and 0 and 1 on both sides to get balance
1-2,0-3,1-1 [BALANCED]
Now we have 1st on both ends. We need to shed them achieve balance
This will lead to
0-3 [UNBALANCED with deficit of 1]
Applying same balance, we get a null set and thus there are no further bit-sequences.
This is way of reducing 1 full sequence to some sub-sequences within it.
But is this the maximum number of sub-sequence?
I am bit skeptical. We can adapt this algorithm further to make sure we shed only from 1 side and not from both sides. That will find all sub-sequences that start from bit position 0.
I am curious to know if this algorithm can be adapted further to run efficiently.