Above is the full question from assignment, no other information provided to students. Full solutions please thanks!

[10] 4. Historical Inaccuracies. Your friend Sauli is constructing a history report on the Scan- dinavian people during the 14th century. He has reviewed numerous journals written during the time and has identified the start and end dates of n unique communal celebrations which have been mentioned. Using all the journals, Sauli has collected a list of facts regarding the celebration events. Each fact has one of the following types: Type 1: events i and j overlap in time. Type 2: event i ended before event ; began. Sauli believes he has understood the journals, but is worried that the data may be inconsistent due to errors made by the authors of the journals. For example, one journal may state that event i ended before y, yet another journal has i and overlapping in time. [4] (a) Help your friend Sauli by constructing an algorithm to determine whether or not there are any inconsistencies with the data given. Hint: If events overlap in time, what does that say about the start times and the finish times of the two events? [2] (b) What is the runtime of your algorithm? [4] (c) Show that your algorithm will correctly report an inconsistency or state that no incon- sistency was found