How to find whether a given date range is overlapped in a collection of list using Java 8?

up vote
6
down vote

favorite

Here is the code which I have written. I want to check whether one can able to see all the three movies.

I am trying to filter the list by removing the overlapping movies and finally checking whether I have removed any movie object, then false else true.

But I think my parallel stream and filter part is not working as after execution of those lines if I am printing the size of the movies collection it is showing 3 but in the above scenario it shouldn't.

By the way, I am new this approach, if there is any other better approach to solve this problem then please help.

public class MovieNight
 public static Boolean canViewAll(Collection<Movie> movies) 
 List<Movie> temp = new ArrayList<>();
 temp.addAll(movies);
 movies.parallelStream().filter((i) -> 
 (movies.parallelStream().filter((j) -> 
 (i.getStart().before(j.getEnd()) && j.getStart().before(i.getEnd()))).count()==0)).collect(Collectors.toList());
 if(movies.size() < temp.size()) 
 return false;
 
 return true;



public static void main(String args) throws Exception 
 SimpleDateFormat sdf = new SimpleDateFormat("y-M-d H:m");

 ArrayList<Movie> movies = new ArrayList<Movie>();
 movies.add(new Movie(sdf.parse("2015-01-01 20:00"), sdf.parse("2015-01-01 22:30")));
 movies.add(new Movie(sdf.parse("2015-01-01 21:30"), sdf.parse("2015-01-01 23:00")));
 movies.add(new Movie(sdf.parse("2015-01-01 23:10"), sdf.parse("2015-01-01 23:30")));

 System.out.println(MovieNight.canViewAll(movies));
 


class Movie 
 private Date start, end;

 public Movie(Date start, Date end) 
 this.start = start;
 this.end = end;
 

 public Date getStart() 
 return this.start;
 

 public Date getEnd() 
 return this.end;

In the above scenario there is a overlapping time of movie one and movie two. In that case it must return false, as no one could see both the movie at same time.

Note: Don't give this type of answer.

List<Movie> mov = (ArrayList)movies;
 for(int i=0;i<mov.size();i++)
 
 Movie movie1 = mov.get(i);
 for(int j=i+1;j<mov.size();j++)
 
 Movie movie2 = mov.get(j);
 if(movie1.getStart().before(movie2.getEnd()) && movie2.getStart().before(movie1.getEnd())) 
 return false;
 
 ;
 
 

 return true;

I have already tried and facing the performance issue and time limit exceeded.

asked 2 hours ago

Debjyoti Pandit

332

New contributor

You're parallel streaming in your parallel stream... You may want to revisit the datastructure your movies in.
â€“Â shinjw
2 hours ago

Then what should I do, Hope you have understood my requirements?
â€“Â Debjyoti Pandit
2 hours ago

No right now it will have only start and end.
â€“Â Debjyoti Pandit
2 hours ago

@DebjyotiPandit Updated answer with a code example.
â€“Â alexrolea
1 hour ago

add a commentÂ |Â

up vote
6
down vote

favorite

Here is the code which I have written. I want to check whether one can able to see all the three movies.

I am trying to filter the list by removing the overlapping movies and finally checking whether I have removed any movie object, then false else true.

By the way, I am new this approach, if there is any other better approach to solve this problem then please help.

public class MovieNight
 public static Boolean canViewAll(Collection<Movie> movies) 
 List<Movie> temp = new ArrayList<>();
 temp.addAll(movies);
 movies.parallelStream().filter((i) -> 
 (movies.parallelStream().filter((j) -> 
 (i.getStart().before(j.getEnd()) && j.getStart().before(i.getEnd()))).count()==0)).collect(Collectors.toList());
 if(movies.size() < temp.size()) 
 return false;
 
 return true;



public static void main(String args) throws Exception 
 SimpleDateFormat sdf = new SimpleDateFormat("y-M-d H:m");

 ArrayList<Movie> movies = new ArrayList<Movie>();
 movies.add(new Movie(sdf.parse("2015-01-01 20:00"), sdf.parse("2015-01-01 22:30")));
 movies.add(new Movie(sdf.parse("2015-01-01 21:30"), sdf.parse("2015-01-01 23:00")));
 movies.add(new Movie(sdf.parse("2015-01-01 23:10"), sdf.parse("2015-01-01 23:30")));

 System.out.println(MovieNight.canViewAll(movies));
 


class Movie 
 private Date start, end;

 public Movie(Date start, Date end) 
 this.start = start;
 this.end = end;
 

 public Date getStart() 
 return this.start;
 

 public Date getEnd() 
 return this.end;

In the above scenario there is a overlapping time of movie one and movie two. In that case it must return false, as no one could see both the movie at same time.

Note: Don't give this type of answer.

List<Movie> mov = (ArrayList)movies;
 for(int i=0;i<mov.size();i++)
 
 Movie movie1 = mov.get(i);
 for(int j=i+1;j<mov.size();j++)
 
 Movie movie2 = mov.get(j);
 if(movie1.getStart().before(movie2.getEnd()) && movie2.getStart().before(movie1.getEnd())) 
 return false;
 
 ;
 
 

 return true;

I have already tried and facing the performance issue and time limit exceeded.

asked 2 hours ago

Debjyoti Pandit

332

New contributor

You're parallel streaming in your parallel stream... You may want to revisit the datastructure your movies in.
â€“Â shinjw
2 hours ago

Then what should I do, Hope you have understood my requirements?
â€“Â Debjyoti Pandit
2 hours ago

No right now it will have only start and end.
â€“Â Debjyoti Pandit
2 hours ago

@DebjyotiPandit Updated answer with a code example.
â€“Â alexrolea
1 hour ago

add a commentÂ |Â

up vote
6
down vote

favorite

Here is the code which I have written. I want to check whether one can able to see all the three movies.

I am trying to filter the list by removing the overlapping movies and finally checking whether I have removed any movie object, then false else true.

By the way, I am new this approach, if there is any other better approach to solve this problem then please help.

public class MovieNight
 public static Boolean canViewAll(Collection<Movie> movies) 
 List<Movie> temp = new ArrayList<>();
 temp.addAll(movies);
 movies.parallelStream().filter((i) -> 
 (movies.parallelStream().filter((j) -> 
 (i.getStart().before(j.getEnd()) && j.getStart().before(i.getEnd()))).count()==0)).collect(Collectors.toList());
 if(movies.size() < temp.size()) 
 return false;
 
 return true;



public static void main(String args) throws Exception 
 SimpleDateFormat sdf = new SimpleDateFormat("y-M-d H:m");

 ArrayList<Movie> movies = new ArrayList<Movie>();
 movies.add(new Movie(sdf.parse("2015-01-01 20:00"), sdf.parse("2015-01-01 22:30")));
 movies.add(new Movie(sdf.parse("2015-01-01 21:30"), sdf.parse("2015-01-01 23:00")));
 movies.add(new Movie(sdf.parse("2015-01-01 23:10"), sdf.parse("2015-01-01 23:30")));

 System.out.println(MovieNight.canViewAll(movies));
 


class Movie 
 private Date start, end;

 public Movie(Date start, Date end) 
 this.start = start;
 this.end = end;
 

 public Date getStart() 
 return this.start;
 

 public Date getEnd() 
 return this.end;

In the above scenario there is a overlapping time of movie one and movie two. In that case it must return false, as no one could see both the movie at same time.

Note: Don't give this type of answer.

List<Movie> mov = (ArrayList)movies;
 for(int i=0;i<mov.size();i++)
 
 Movie movie1 = mov.get(i);
 for(int j=i+1;j<mov.size();j++)
 
 Movie movie2 = mov.get(j);
 if(movie1.getStart().before(movie2.getEnd()) && movie2.getStart().before(movie1.getEnd())) 
 return false;
 
 ;
 
 

 return true;

I have already tried and facing the performance issue and time limit exceeded.

asked 2 hours ago

Debjyoti Pandit

332

New contributor

Here is the code which I have written. I want to check whether one can able to see all the three movies.

I am trying to filter the list by removing the overlapping movies and finally checking whether I have removed any movie object, then false else true.

By the way, I am new this approach, if there is any other better approach to solve this problem then please help.

public class MovieNight
 public static Boolean canViewAll(Collection<Movie> movies) 
 List<Movie> temp = new ArrayList<>();
 temp.addAll(movies);
 movies.parallelStream().filter((i) -> 
 (movies.parallelStream().filter((j) -> 
 (i.getStart().before(j.getEnd()) && j.getStart().before(i.getEnd()))).count()==0)).collect(Collectors.toList());
 if(movies.size() < temp.size()) 
 return false;
 
 return true;



public static void main(String args) throws Exception 
 SimpleDateFormat sdf = new SimpleDateFormat("y-M-d H:m");

 ArrayList<Movie> movies = new ArrayList<Movie>();
 movies.add(new Movie(sdf.parse("2015-01-01 20:00"), sdf.parse("2015-01-01 22:30")));
 movies.add(new Movie(sdf.parse("2015-01-01 21:30"), sdf.parse("2015-01-01 23:00")));
 movies.add(new Movie(sdf.parse("2015-01-01 23:10"), sdf.parse("2015-01-01 23:30")));

 System.out.println(MovieNight.canViewAll(movies));
 


class Movie 
 private Date start, end;

 public Movie(Date start, Date end) 
 this.start = start;
 this.end = end;
 

 public Date getStart() 
 return this.start;
 

 public Date getEnd() 
 return this.end;

In the above scenario there is a overlapping time of movie one and movie two. In that case it must return false, as no one could see both the movie at same time.

Note: Don't give this type of answer.

List<Movie> mov = (ArrayList)movies;
 for(int i=0;i<mov.size();i++)
 
 Movie movie1 = mov.get(i);
 for(int j=i+1;j<mov.size();j++)
 
 Movie movie2 = mov.get(j);
 if(movie1.getStart().before(movie2.getEnd()) && movie2.getStart().before(movie1.getEnd())) 
 return false;
 
 ;
 
 

 return true;

I have already tried and facing the performance issue and time limit exceeded.

java oop collections java-8

asked 2 hours ago

Debjyoti Pandit

332

New contributor

asked 2 hours ago

Debjyoti Pandit

332

New contributor

asked 2 hours ago

Debjyoti Pandit

332

New contributor

asked 2 hours ago

Debjyoti Pandit

332

asked 2 hours ago

Debjyoti Pandit

332

New contributor

Debjyoti Pandit is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

You're parallel streaming in your parallel stream... You may want to revisit the datastructure your movies in.
â€“Â shinjw
2 hours ago

Then what should I do, Hope you have understood my requirements?
â€“Â Debjyoti Pandit
2 hours ago

No right now it will have only start and end.
â€“Â Debjyoti Pandit
2 hours ago

@DebjyotiPandit Updated answer with a code example.
â€“Â alexrolea
1 hour ago

add a commentÂ |Â

You're parallel streaming in your parallel stream... You may want to revisit the datastructure your movies in.
â€“Â shinjw
2 hours ago

Then what should I do, Hope you have understood my requirements?
â€“Â Debjyoti Pandit
2 hours ago

No right now it will have only start and end.
â€“Â Debjyoti Pandit
2 hours ago

@DebjyotiPandit Updated answer with a code example.
â€“Â alexrolea
1 hour ago

You're parallel streaming in your parallel stream... You may want to revisit the datastructure your movies in.
â€“Â shinjw
2 hours ago

Then what should I do, Hope you have understood my requirements?
â€“Â Debjyoti Pandit
2 hours ago

No right now it will have only start and end.
â€“Â Debjyoti Pandit
2 hours ago

@DebjyotiPandit Updated answer with a code example.
â€“Â alexrolea
1 hour ago

add a commentÂ |Â

4 Answers
4

active

oldest

votes

up vote
7
down vote

Your approach has a complexity of O(n^2).

You can do this in O(nlogn).

First, sort the list of intervals by ending date. This can be done in O(nlogn)

Iterate the list and check weather for each element i, i.getEndDate()<(i+i).getBeginDate(). If the condition is true for all elements, you can see all the movies. Otherwise, you can't - and you have overlapping inetrvals. This can be done in O(n).

Therefore, for the whole algorithm, the complexity will be O(nlogn) + O(n) = O(nlogn)

Please see the below snippets (Adjust from double to Date and add any null checks and check for corner cases as needed. I've omitted them for brevity.).

class Interval 

 private double begin;
 private double end;

 public Interval(double begin, double end)
 this.begin = begin;
 this.end = end;
 

 public double getBegin() 
 return begin;
 

 public double getEnd() 
 return end;
 



public static final boolean hasOverlappingIntervals(List<Interval> intervals)
 // this is O(nlogn)
 intervals = intervals
 .stream()
 .sorted(Comparator.comparing(Interval::getEnd))
 .collect(Collectors.toList());

 // this is O(n)
 for(int i = 0 ; i < intervals.size() - 1 ; i ++)
 if(intervals.get(i).getEnd() > intervals.get(i+1).getBegin())
 return true;
 
 
 return false;


public static void main(String args) 
 System.out.println(hasOverlappingIntervals(Arrays.asList(new Interval(1,2), new Interval(3,4), new Interval(5,6))));
 System.out.println(hasOverlappingIntervals(Arrays.asList(new Interval(1,2), new Interval(2,3), new Interval(3,4))));
 System.out.println(hasOverlappingIntervals(Arrays.asList(new Interval(1,3), new Interval(2,5), new Interval(6,7))));
 System.out.println(hasOverlappingIntervals(Arrays.asList(new Interval(5,7), new Interval(6,8), new Interval(1,2))));
 System.out.println(hasOverlappingIntervals(Arrays.asList(new Interval(6,7), new Interval(5,8), new Interval(1,2))));
 System.out.println(hasOverlappingIntervals(Arrays.asList(new Interval(4,6), new Interval(3,5), new Interval(2,9))));

edited 22 mins ago

Hulk

2,14511432

answered 2 hours ago

alexrolea

1,06017

add a commentÂ |Â

up vote
1
down vote

Again O(n^2) only but slightly different approach and does not need any changes in your Movie class.

public static Boolean canViewAll(Collection<Movie> movies) 
 List<Movie> temp = new ArrayList<>();
 temp.addAll(movies);

 List<Movie> temp2 = temp.stream().collect(ArrayList::new, 
 (list, movie) -> 
 boolean contians = list.stream().anyMatch
 (listMovie -> 
 movie.getStart().before(listMovie.getEnd())
 && listMovie.getStart().before(movie.getEnd())
 );
 if (!contians)
 list.add(movie);

 , List::addAll);

 if (movies.size() != temp2.size()) 
 return false;
 
 return true

answered 1 hour ago

Chota Bheem

584519

add a commentÂ |Â

up vote
1
down vote

This approach would still have a O(n^2) runtime in the worst case, but should be more performant since it will short circuit a bit more effectively and you would be able to parallelize this more effectively.

public static Boolean canViewAll(Collection<Movie> movies) 
 return movies.stream() // <-- you can parallelize this.
 .noneMatch(i -> movies.stream().filter(j -> !i.equals(j)) // Filters out current position.
 .anyMatch(j -> j.isConflicting(i.getStart(), i.getEnd())));


public class Movie 
 ...
 public boolean isConflicting(Date start, Date end) 
 // Looks like you also had a bug in your check. You'll want to check if both the start and end times are within the window of another movie.
 return start.after(this.getStart()) && start.before(this.getEnd()) 
 && end.after(this.getStart()) && end.before(this.getEnd());

edited 1 hour ago

answered 1 hour ago

shinjw

1,595724

I think you are checking only conflicting start and end but I need conflicting range of start and end date.
â€“Â Debjyoti Pandit
1 hour ago

This approach does that. (Hence the O(n^2) runtime)... edited lambda variable names to reflect OP's naming. You will be checking each and every j to see if it conflicts with i
â€“Â shinjw
1 hour ago

Updated approach with a filter for the current position (i). You'll also want to revisit your logic for checking for conflicts.
â€“Â shinjw
1 hour ago

add a commentÂ |Â

up vote
-1
down vote

If performance is not an issue try with flatMap to compare all with all (n^2).
In the next step you should do some improvements to make it faster.

 public static Boolean canViewAll(Collection<Movie> movies) 
 List<Movie> temp = new ArrayList<>();
 temp.addAll(movies);

 Optional<Movie> any = movies.stream()
 .flatMap(movie -> movies.stream()
 .filter(otherMovie -> !movie.equals(otherMovie))
 .filter(otherMovie -> movie.getStart().before(otherMovie.getEnd()) && otherMovie.getStart().before(movie.getEnd())))
 .findAny();
 return !any.isPresent();

answered 2 hours ago

niemar

152213

Performance is the major issues, I need to pass a large collection of movies.
â€“Â Debjyoti Pandit
2 hours ago

Ok, but your initial approach with parallel streams seems to be incorrect.
â€“Â niemar
2 hours ago

Yeah I know, I am new to this. Tried what I knew.
â€“Â Debjyoti Pandit
2 hours ago

I shall be obliged if you guide me in right path.
â€“Â Debjyoti Pandit
2 hours ago

Using anyMatch(Predicate) rather than filter to an optional would provide some performance benefits since it will shortcircuit the method as soon as a match is found. But i'd imagine this is an algorithm challenge to find the optimal approach (time complexity wise)
â€“Â shinjw
2 hours ago

Â |Â
show 1 more comment

Your Answer

StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "1"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: true,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);

);

Debjyoti Pandit is a new contributor. Be nice, and check out our Code of Conduct.

draft saved

draft discarded

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f52622085%2fhow-to-find-whether-a-given-date-range-is-overlapped-in-a-collection-of-list-usi%23new-answer', 'question_page');

);

Post as a guest

Name

4 Answers
4

active

oldest

votes

4 Answers
4

active

oldest

votes

up vote
7
down vote

Your approach has a complexity of O(n^2).

You can do this in O(nlogn).

First, sort the list of intervals by ending date. This can be done in O(nlogn)

Iterate the list and check weather for each element i, i.getEndDate()<(i+i).getBeginDate(). If the condition is true for all elements, you can see all the movies. Otherwise, you can't - and you have overlapping inetrvals. This can be done in O(n).

Therefore, for the whole algorithm, the complexity will be O(nlogn) + O(n) = O(nlogn)

Please see the below snippets (Adjust from double to Date and add any null checks and check for corner cases as needed. I've omitted them for brevity.).

class Interval 

 private double begin;
 private double end;

 public Interval(double begin, double end)
 this.begin = begin;
 this.end = end;
 

 public double getBegin() 
 return begin;
 

 public double getEnd() 
 return end;
 



public static final boolean hasOverlappingIntervals(List<Interval> intervals)
 // this is O(nlogn)
 intervals = intervals
 .stream()
 .sorted(Comparator.comparing(Interval::getEnd))
 .collect(Collectors.toList());

 // this is O(n)
 for(int i = 0 ; i < intervals.size() - 1 ; i ++)
 if(intervals.get(i).getEnd() > intervals.get(i+1).getBegin())
 return true;
 
 
 return false;


public static void main(String args) 
 System.out.println(hasOverlappingIntervals(Arrays.asList(new Interval(1,2), new Interval(3,4), new Interval(5,6))));
 System.out.println(hasOverlappingIntervals(Arrays.asList(new Interval(1,2), new Interval(2,3), new Interval(3,4))));
 System.out.println(hasOverlappingIntervals(Arrays.asList(new Interval(1,3), new Interval(2,5), new Interval(6,7))));
 System.out.println(hasOverlappingIntervals(Arrays.asList(new Interval(5,7), new Interval(6,8), new Interval(1,2))));
 System.out.println(hasOverlappingIntervals(Arrays.asList(new Interval(6,7), new Interval(5,8), new Interval(1,2))));
 System.out.println(hasOverlappingIntervals(Arrays.asList(new Interval(4,6), new Interval(3,5), new Interval(2,9))));

edited 22 mins ago

Hulk

2,14511432

answered 2 hours ago

alexrolea

1,06017

add a commentÂ |Â

up vote
7
down vote

Your approach has a complexity of O(n^2).

You can do this in O(nlogn).

First, sort the list of intervals by ending date. This can be done in O(nlogn)

Iterate the list and check weather for each element i, i.getEndDate()<(i+i).getBeginDate(). If the condition is true for all elements, you can see all the movies. Otherwise, you can't - and you have overlapping inetrvals. This can be done in O(n).

Therefore, for the whole algorithm, the complexity will be O(nlogn) + O(n) = O(nlogn)

Please see the below snippets (Adjust from double to Date and add any null checks and check for corner cases as needed. I've omitted them for brevity.).

class Interval 

 private double begin;
 private double end;

 public Interval(double begin, double end)
 this.begin = begin;
 this.end = end;
 

 public double getBegin() 
 return begin;
 

 public double getEnd() 
 return end;
 



public static final boolean hasOverlappingIntervals(List<Interval> intervals)
 // this is O(nlogn)
 intervals = intervals
 .stream()
 .sorted(Comparator.comparing(Interval::getEnd))
 .collect(Collectors.toList());

 // this is O(n)
 for(int i = 0 ; i < intervals.size() - 1 ; i ++)
 if(intervals.get(i).getEnd() > intervals.get(i+1).getBegin())
 return true;
 
 
 return false;


public static void main(String args) 
 System.out.println(hasOverlappingIntervals(Arrays.asList(new Interval(1,2), new Interval(3,4), new Interval(5,6))));
 System.out.println(hasOverlappingIntervals(Arrays.asList(new Interval(1,2), new Interval(2,3), new Interval(3,4))));
 System.out.println(hasOverlappingIntervals(Arrays.asList(new Interval(1,3), new Interval(2,5), new Interval(6,7))));
 System.out.println(hasOverlappingIntervals(Arrays.asList(new Interval(5,7), new Interval(6,8), new Interval(1,2))));
 System.out.println(hasOverlappingIntervals(Arrays.asList(new Interval(6,7), new Interval(5,8), new Interval(1,2))));
 System.out.println(hasOverlappingIntervals(Arrays.asList(new Interval(4,6), new Interval(3,5), new Interval(2,9))));

edited 22 mins ago

Hulk

2,14511432

answered 2 hours ago

alexrolea

1,06017

add a commentÂ |Â

up vote
7
down vote

Your approach has a complexity of O(n^2).

You can do this in O(nlogn).

First, sort the list of intervals by ending date. This can be done in O(nlogn)

Iterate the list and check weather for each element i, i.getEndDate()<(i+i).getBeginDate(). If the condition is true for all elements, you can see all the movies. Otherwise, you can't - and you have overlapping inetrvals. This can be done in O(n).

Therefore, for the whole algorithm, the complexity will be O(nlogn) + O(n) = O(nlogn)

Please see the below snippets (Adjust from double to Date and add any null checks and check for corner cases as needed. I've omitted them for brevity.).

class Interval 

 private double begin;
 private double end;

 public Interval(double begin, double end)
 this.begin = begin;
 this.end = end;
 

 public double getBegin() 
 return begin;
 

 public double getEnd() 
 return end;
 



public static final boolean hasOverlappingIntervals(List<Interval> intervals)
 // this is O(nlogn)
 intervals = intervals
 .stream()
 .sorted(Comparator.comparing(Interval::getEnd))
 .collect(Collectors.toList());

 // this is O(n)
 for(int i = 0 ; i < intervals.size() - 1 ; i ++)
 if(intervals.get(i).getEnd() > intervals.get(i+1).getBegin())
 return true;
 
 
 return false;


public static void main(String args) 
 System.out.println(hasOverlappingIntervals(Arrays.asList(new Interval(1,2), new Interval(3,4), new Interval(5,6))));
 System.out.println(hasOverlappingIntervals(Arrays.asList(new Interval(1,2), new Interval(2,3), new Interval(3,4))));
 System.out.println(hasOverlappingIntervals(Arrays.asList(new Interval(1,3), new Interval(2,5), new Interval(6,7))));
 System.out.println(hasOverlappingIntervals(Arrays.asList(new Interval(5,7), new Interval(6,8), new Interval(1,2))));
 System.out.println(hasOverlappingIntervals(Arrays.asList(new Interval(6,7), new Interval(5,8), new Interval(1,2))));
 System.out.println(hasOverlappingIntervals(Arrays.asList(new Interval(4,6), new Interval(3,5), new Interval(2,9))));

edited 22 mins ago

Hulk

2,14511432

answered 2 hours ago

alexrolea

1,06017

Your approach has a complexity of O(n^2).

You can do this in O(nlogn).

First, sort the list of intervals by ending date. This can be done in O(nlogn)

Iterate the list and check weather for each element i, i.getEndDate()<(i+i).getBeginDate(). If the condition is true for all elements, you can see all the movies. Otherwise, you can't - and you have overlapping inetrvals. This can be done in O(n).

Therefore, for the whole algorithm, the complexity will be O(nlogn) + O(n) = O(nlogn)

Please see the below snippets (Adjust from double to Date and add any null checks and check for corner cases as needed. I've omitted them for brevity.).

class Interval 

 private double begin;
 private double end;

 public Interval(double begin, double end)
 this.begin = begin;
 this.end = end;
 

 public double getBegin() 
 return begin;
 

 public double getEnd() 
 return end;
 



public static final boolean hasOverlappingIntervals(List<Interval> intervals)
 // this is O(nlogn)
 intervals = intervals
 .stream()
 .sorted(Comparator.comparing(Interval::getEnd))
 .collect(Collectors.toList());

 // this is O(n)
 for(int i = 0 ; i < intervals.size() - 1 ; i ++)
 if(intervals.get(i).getEnd() > intervals.get(i+1).getBegin())
 return true;
 
 
 return false;


public static void main(String args) 
 System.out.println(hasOverlappingIntervals(Arrays.asList(new Interval(1,2), new Interval(3,4), new Interval(5,6))));
 System.out.println(hasOverlappingIntervals(Arrays.asList(new Interval(1,2), new Interval(2,3), new Interval(3,4))));
 System.out.println(hasOverlappingIntervals(Arrays.asList(new Interval(1,3), new Interval(2,5), new Interval(6,7))));
 System.out.println(hasOverlappingIntervals(Arrays.asList(new Interval(5,7), new Interval(6,8), new Interval(1,2))));
 System.out.println(hasOverlappingIntervals(Arrays.asList(new Interval(6,7), new Interval(5,8), new Interval(1,2))));
 System.out.println(hasOverlappingIntervals(Arrays.asList(new Interval(4,6), new Interval(3,5), new Interval(2,9))));

edited 22 mins ago

Hulk

2,14511432

answered 2 hours ago

alexrolea

1,06017

edited 22 mins ago

Hulk

2,14511432

edited 22 mins ago

Hulk

2,14511432

edited 22 mins ago

Hulk

2,14511432

answered 2 hours ago

alexrolea

1,06017

answered 2 hours ago

alexrolea

1,06017

answered 2 hours ago

alexrolea

1,06017

add a commentÂ |Â

up vote
1
down vote

Again O(n^2) only but slightly different approach and does not need any changes in your Movie class.

public static Boolean canViewAll(Collection<Movie> movies) 
 List<Movie> temp = new ArrayList<>();
 temp.addAll(movies);

 List<Movie> temp2 = temp.stream().collect(ArrayList::new, 
 (list, movie) -> 
 boolean contians = list.stream().anyMatch
 (listMovie -> 
 movie.getStart().before(listMovie.getEnd())
 && listMovie.getStart().before(movie.getEnd())
 );
 if (!contians)
 list.add(movie);

 , List::addAll);

 if (movies.size() != temp2.size()) 
 return false;
 
 return true

answered 1 hour ago

Chota Bheem

584519

add a commentÂ |Â

up vote
1
down vote

Again O(n^2) only but slightly different approach and does not need any changes in your Movie class.

public static Boolean canViewAll(Collection<Movie> movies) 
 List<Movie> temp = new ArrayList<>();
 temp.addAll(movies);

 List<Movie> temp2 = temp.stream().collect(ArrayList::new, 
 (list, movie) -> 
 boolean contians = list.stream().anyMatch
 (listMovie -> 
 movie.getStart().before(listMovie.getEnd())
 && listMovie.getStart().before(movie.getEnd())
 );
 if (!contians)
 list.add(movie);

 , List::addAll);

 if (movies.size() != temp2.size()) 
 return false;
 
 return true

answered 1 hour ago

Chota Bheem

584519

add a commentÂ |Â

up vote
1
down vote

Again O(n^2) only but slightly different approach and does not need any changes in your Movie class.

public static Boolean canViewAll(Collection<Movie> movies) 
 List<Movie> temp = new ArrayList<>();
 temp.addAll(movies);

 List<Movie> temp2 = temp.stream().collect(ArrayList::new, 
 (list, movie) -> 
 boolean contians = list.stream().anyMatch
 (listMovie -> 
 movie.getStart().before(listMovie.getEnd())
 && listMovie.getStart().before(movie.getEnd())
 );
 if (!contians)
 list.add(movie);

 , List::addAll);

 if (movies.size() != temp2.size()) 
 return false;
 
 return true

answered 1 hour ago

Chota Bheem

584519

Again O(n^2) only but slightly different approach and does not need any changes in your Movie class.

public static Boolean canViewAll(Collection<Movie> movies) 
 List<Movie> temp = new ArrayList<>();
 temp.addAll(movies);

 List<Movie> temp2 = temp.stream().collect(ArrayList::new, 
 (list, movie) -> 
 boolean contians = list.stream().anyMatch
 (listMovie -> 
 movie.getStart().before(listMovie.getEnd())
 && listMovie.getStart().before(movie.getEnd())
 );
 if (!contians)
 list.add(movie);

 , List::addAll);

 if (movies.size() != temp2.size()) 
 return false;
 
 return true

answered 1 hour ago

Chota Bheem

584519

answered 1 hour ago

Chota Bheem

584519

answered 1 hour ago

Chota Bheem

584519

answered 1 hour ago

Chota Bheem

584519

add a commentÂ |Â

up vote
1
down vote

public static Boolean canViewAll(Collection<Movie> movies) 
 return movies.stream() // <-- you can parallelize this.
 .noneMatch(i -> movies.stream().filter(j -> !i.equals(j)) // Filters out current position.
 .anyMatch(j -> j.isConflicting(i.getStart(), i.getEnd())));


public class Movie 
 ...
 public boolean isConflicting(Date start, Date end) 
 // Looks like you also had a bug in your check. You'll want to check if both the start and end times are within the window of another movie.
 return start.after(this.getStart()) && start.before(this.getEnd()) 
 && end.after(this.getStart()) && end.before(this.getEnd());

edited 1 hour ago

answered 1 hour ago

shinjw

1,595724

I think you are checking only conflicting start and end but I need conflicting range of start and end date.
â€“Â Debjyoti Pandit
1 hour ago

This approach does that. (Hence the O(n^2) runtime)... edited lambda variable names to reflect OP's naming. You will be checking each and every j to see if it conflicts with i
â€“Â shinjw
1 hour ago

Updated approach with a filter for the current position (i). You'll also want to revisit your logic for checking for conflicts.
â€“Â shinjw
1 hour ago

add a commentÂ |Â

up vote
1
down vote

public static Boolean canViewAll(Collection<Movie> movies) 
 return movies.stream() // <-- you can parallelize this.
 .noneMatch(i -> movies.stream().filter(j -> !i.equals(j)) // Filters out current position.
 .anyMatch(j -> j.isConflicting(i.getStart(), i.getEnd())));


public class Movie 
 ...
 public boolean isConflicting(Date start, Date end) 
 // Looks like you also had a bug in your check. You'll want to check if both the start and end times are within the window of another movie.
 return start.after(this.getStart()) && start.before(this.getEnd()) 
 && end.after(this.getStart()) && end.before(this.getEnd());

edited 1 hour ago

answered 1 hour ago

shinjw

1,595724

I think you are checking only conflicting start and end but I need conflicting range of start and end date.
â€“Â Debjyoti Pandit
1 hour ago

This approach does that. (Hence the O(n^2) runtime)... edited lambda variable names to reflect OP's naming. You will be checking each and every j to see if it conflicts with i
â€“Â shinjw
1 hour ago

Updated approach with a filter for the current position (i). You'll also want to revisit your logic for checking for conflicts.
â€“Â shinjw
1 hour ago

add a commentÂ |Â

up vote
1
down vote

public static Boolean canViewAll(Collection<Movie> movies) 
 return movies.stream() // <-- you can parallelize this.
 .noneMatch(i -> movies.stream().filter(j -> !i.equals(j)) // Filters out current position.
 .anyMatch(j -> j.isConflicting(i.getStart(), i.getEnd())));


public class Movie 
 ...
 public boolean isConflicting(Date start, Date end) 
 // Looks like you also had a bug in your check. You'll want to check if both the start and end times are within the window of another movie.
 return start.after(this.getStart()) && start.before(this.getEnd()) 
 && end.after(this.getStart()) && end.before(this.getEnd());

edited 1 hour ago

answered 1 hour ago

shinjw

1,595724

public static Boolean canViewAll(Collection<Movie> movies) 
 return movies.stream() // <-- you can parallelize this.
 .noneMatch(i -> movies.stream().filter(j -> !i.equals(j)) // Filters out current position.
 .anyMatch(j -> j.isConflicting(i.getStart(), i.getEnd())));


public class Movie 
 ...
 public boolean isConflicting(Date start, Date end) 
 // Looks like you also had a bug in your check. You'll want to check if both the start and end times are within the window of another movie.
 return start.after(this.getStart()) && start.before(this.getEnd()) 
 && end.after(this.getStart()) && end.before(this.getEnd());

edited 1 hour ago

answered 1 hour ago

shinjw

1,595724

edited 1 hour ago

answered 1 hour ago

shinjw

1,595724

answered 1 hour ago

shinjw

1,595724

answered 1 hour ago

shinjw

1,595724

I think you are checking only conflicting start and end but I need conflicting range of start and end date.
â€“Â Debjyoti Pandit
1 hour ago

This approach does that. (Hence the O(n^2) runtime)... edited lambda variable names to reflect OP's naming. You will be checking each and every j to see if it conflicts with i
â€“Â shinjw
1 hour ago

Updated approach with a filter for the current position (i). You'll also want to revisit your logic for checking for conflicts.
â€“Â shinjw
1 hour ago

add a commentÂ |Â

I think you are checking only conflicting start and end but I need conflicting range of start and end date.
â€“Â Debjyoti Pandit
1 hour ago

This approach does that. (Hence the O(n^2) runtime)... edited lambda variable names to reflect OP's naming. You will be checking each and every j to see if it conflicts with i
â€“Â shinjw
1 hour ago

Updated approach with a filter for the current position (i). You'll also want to revisit your logic for checking for conflicts.
â€“Â shinjw
1 hour ago

I think you are checking only conflicting start and end but I need conflicting range of start and end date.
â€“Â Debjyoti Pandit
1 hour ago

This approach does that. (Hence the O(n^2) runtime)... edited lambda variable names to reflect OP's naming. You will be checking each and every j to see if it conflicts with i
â€“Â shinjw
1 hour ago

Updated approach with a filter for the current position (i). You'll also want to revisit your logic for checking for conflicts.
â€“Â shinjw
1 hour ago

add a commentÂ |Â

up vote
-1
down vote

If performance is not an issue try with flatMap to compare all with all (n^2).
In the next step you should do some improvements to make it faster.

 public static Boolean canViewAll(Collection<Movie> movies) 
 List<Movie> temp = new ArrayList<>();
 temp.addAll(movies);

 Optional<Movie> any = movies.stream()
 .flatMap(movie -> movies.stream()
 .filter(otherMovie -> !movie.equals(otherMovie))
 .filter(otherMovie -> movie.getStart().before(otherMovie.getEnd()) && otherMovie.getStart().before(movie.getEnd())))
 .findAny();
 return !any.isPresent();

answered 2 hours ago

niemar

152213

Performance is the major issues, I need to pass a large collection of movies.
â€“Â Debjyoti Pandit
2 hours ago

Ok, but your initial approach with parallel streams seems to be incorrect.
â€“Â niemar
2 hours ago

Yeah I know, I am new to this. Tried what I knew.
â€“Â Debjyoti Pandit
2 hours ago

I shall be obliged if you guide me in right path.
â€“Â Debjyoti Pandit
2 hours ago

Using anyMatch(Predicate) rather than filter to an optional would provide some performance benefits since it will shortcircuit the method as soon as a match is found. But i'd imagine this is an algorithm challenge to find the optimal approach (time complexity wise)
â€“Â shinjw
2 hours ago

Â |Â
show 1 more comment

up vote
-1
down vote

If performance is not an issue try with flatMap to compare all with all (n^2).
In the next step you should do some improvements to make it faster.

 public static Boolean canViewAll(Collection<Movie> movies) 
 List<Movie> temp = new ArrayList<>();
 temp.addAll(movies);

 Optional<Movie> any = movies.stream()
 .flatMap(movie -> movies.stream()
 .filter(otherMovie -> !movie.equals(otherMovie))
 .filter(otherMovie -> movie.getStart().before(otherMovie.getEnd()) && otherMovie.getStart().before(movie.getEnd())))
 .findAny();
 return !any.isPresent();

answered 2 hours ago

niemar

152213

Performance is the major issues, I need to pass a large collection of movies.
â€“Â Debjyoti Pandit
2 hours ago

Ok, but your initial approach with parallel streams seems to be incorrect.
â€“Â niemar
2 hours ago

Yeah I know, I am new to this. Tried what I knew.
â€“Â Debjyoti Pandit
2 hours ago

I shall be obliged if you guide me in right path.
â€“Â Debjyoti Pandit
2 hours ago

Using anyMatch(Predicate) rather than filter to an optional would provide some performance benefits since it will shortcircuit the method as soon as a match is found. But i'd imagine this is an algorithm challenge to find the optimal approach (time complexity wise)
â€“Â shinjw
2 hours ago

Â |Â
show 1 more comment

up vote
-1
down vote

If performance is not an issue try with flatMap to compare all with all (n^2).
In the next step you should do some improvements to make it faster.

 public static Boolean canViewAll(Collection<Movie> movies) 
 List<Movie> temp = new ArrayList<>();
 temp.addAll(movies);

 Optional<Movie> any = movies.stream()
 .flatMap(movie -> movies.stream()
 .filter(otherMovie -> !movie.equals(otherMovie))
 .filter(otherMovie -> movie.getStart().before(otherMovie.getEnd()) && otherMovie.getStart().before(movie.getEnd())))
 .findAny();
 return !any.isPresent();

answered 2 hours ago

niemar

152213

If performance is not an issue try with flatMap to compare all with all (n^2).
In the next step you should do some improvements to make it faster.

 public static Boolean canViewAll(Collection<Movie> movies) 
 List<Movie> temp = new ArrayList<>();
 temp.addAll(movies);

 Optional<Movie> any = movies.stream()
 .flatMap(movie -> movies.stream()
 .filter(otherMovie -> !movie.equals(otherMovie))
 .filter(otherMovie -> movie.getStart().before(otherMovie.getEnd()) && otherMovie.getStart().before(movie.getEnd())))
 .findAny();
 return !any.isPresent();

answered 2 hours ago

niemar

152213

answered 2 hours ago

niemar

152213

answered 2 hours ago

niemar

152213

answered 2 hours ago

niemar

152213

Performance is the major issues, I need to pass a large collection of movies.
â€“Â Debjyoti Pandit
2 hours ago

Ok, but your initial approach with parallel streams seems to be incorrect.
â€“Â niemar
2 hours ago

Yeah I know, I am new to this. Tried what I knew.
â€“Â Debjyoti Pandit
2 hours ago

I shall be obliged if you guide me in right path.
â€“Â Debjyoti Pandit
2 hours ago

Using anyMatch(Predicate) rather than filter to an optional would provide some performance benefits since it will shortcircuit the method as soon as a match is found. But i'd imagine this is an algorithm challenge to find the optimal approach (time complexity wise)
â€“Â shinjw
2 hours ago

Â |Â
show 1 more comment

Performance is the major issues, I need to pass a large collection of movies.
â€“Â Debjyoti Pandit
2 hours ago

Ok, but your initial approach with parallel streams seems to be incorrect.
â€“Â niemar
2 hours ago

Yeah I know, I am new to this. Tried what I knew.
â€“Â Debjyoti Pandit
2 hours ago

I shall be obliged if you guide me in right path.
â€“Â Debjyoti Pandit
2 hours ago

Using anyMatch(Predicate) rather than filter to an optional would provide some performance benefits since it will shortcircuit the method as soon as a match is found. But i'd imagine this is an algorithm challenge to find the optimal approach (time complexity wise)
â€“Â shinjw
2 hours ago

Performance is the major issues, I need to pass a large collection of movies.
â€“Â Debjyoti Pandit
2 hours ago

Ok, but your initial approach with parallel streams seems to be incorrect.
â€“Â niemar
2 hours ago

Yeah I know, I am new to this. Tried what I knew.
â€“Â Debjyoti Pandit
2 hours ago

I shall be obliged if you guide me in right path.
â€“Â Debjyoti Pandit
2 hours ago

Using anyMatch(Predicate) rather than filter to an optional would provide some performance benefits since it will shortcircuit the method as soon as a match is found. But i'd imagine this is an algorithm challenge to find the optimal approach (time complexity wise)
â€“Â shinjw
2 hours ago

Â |Â
show 1 more comment

Debjyoti Pandit is a new contributor. Be nice, and check out our Code of Conduct.

draft saved

draft discarded

Debjyoti Pandit is a new contributor. Be nice, and check out our Code of Conduct.

draft saved

draft discarded

Post as a guest

Name

Search This Blog

Iyfjky