Thread: Find maximum working time [Urgent]

I got a problem.

Assume i got 4 time interval in figure4 List.

List<Interval> figure4 = new ArrayList<Interval>();
figure4.add(new Interval("06:00", "08:30"));
figure4.add(new Interval("08:00", "10:30"));
figure4.add(new Interval("10:00", "12:00"));
figure4.add(new Interval("11:30", "15:00"));

how to i get the maximum working time without overlapping other interval ?
By using algorithm

Please don't post duplicate topics: Duplicate.

What have you tried?

Marking something "Urgent" doesn't really help and might even hurt. Sane, intelligent people are typically not interested in becoming embroiled in other people's crises.

I suggest you simplify the problem to combine intervals that may overlap using integers, then maybe increase the complexity to doubles (with decimals) and then expand that to a different numbering system, like TIME. You'll discover new challenges and learn how to overcome them with each step.

Sorry about putting Urgent

I have done the function to determine maximum interval overlap.
And the total minute for each interval also can be count.


if countOverlap return 1 mean no overlap
if return 2 mean maximum 2 interval are overlap from the List Interval.
if return 3 mean maximum 3 interval are overlap from the List Interval in a period.


Code:
List<Interval> figure4 = new ArrayList<Interval>();
figure4.add(new Interval("06:00", "08:30")); //150 minute
figure4.add(new Interval("08:00", "10:30")); //150 minute
figure4.add(new Interval("07:30", "08:30")); //60 minute
int countOverlap = getMaxIntervalOverlapCount(figure4);

Answer: 3


public static int getMaxIntervalOverlapCount(List<Interval> intervals) {
int returnValue;
int big;
int tempBig;
int count;
List<Interval> list1;
returnValue = 0;
big = 0;
tempBig = 0;

for(int x = 0; x < intervals.size(); x = x+1) {
int b1 = intervals.get(x).getBeginMinuteUnit();
int e1 = intervals.get(x).getEndMinuteUnit();
for (int y = 0; y < intervals.size();y = y + 1){
if(x != y){
int b2 = intervals.get(y).getBeginMinuteUnit();
int e2 = intervals.get(y).getEndMinuteUnit();
if ((b1 <b2 && b2<e1) ||(b1 <e2 && e2<e1) ){
int fromTime = 0;
int toTime = 0;
if (b1 <= b2){
fromTime = b2;
}else{
fromTime = b1;
}
if (e1 <= e2){
toTime = e1;
}else{
toTime = e2;
}

count = calculate(intervals,fromTime,toTime);
if (returnValue < count){
returnValue = count;
}
}
}
}
}
returnValue = returnValue;
return returnValue;
}

public static int calculate(List<Interval> intervals,int fromTime,int toTime){
int value;
value = 0;
for(int x = 0; x < intervals.size(); x = x+1) {
int b1 = intervals.get(x).getBeginMinuteUnit();
int e1 = intervals.get(x).getEndMinuteUnit();
if (b1 <= fromTime && toTime <= e1){
value = value + 1;
}

}

return value;
}



Now i am thinking
assume i got 6 interval in List
how to i get the maximum working time without overlapping each other.

Previously i have declare 2 dimension array
int [][] overlap = new int[][];
if overlap[i][j] > 1
mean there is overlap between interval i and interval j

now i am no idea, how to get the logic for calculate maximum working time

Please post your code in code tags.

I see you've already made some progress, but not in the crawl, walk, run fashion I suggested. Since you started to work the solution by running rather than thoughtfully crawling, you may be running around in directions that aren't especially helpful. For example, I don't know that the method getMaxIntervalOverlapCount() is particularly useful, at least I don't see its value to deriving a solution.

I visualize the problem as a number of line segments laid on a number line, some overlap, some don't. There are then a number of useful methods I'd write to characterize the data set that includes those line segments from the min and max times in which they exist: one that adds the length of the line segment regardless of overlap; another that calculates the total overlap; and another that calculates the total time when no work is being done; etc. Once the data set has been adequately characterized, I could then answer any question about the data set anyone could ask.

You need to visualize the data in some useful way and then characterize it as needed to answer your question(s).