There were three problems, all of them were coding only.
Given a string S, consisting of only lowercase english letters. Find the number of substrings having all characters distinct.
Given a list of N intervals, each interval have some weight assigned to it, you are asked to choose two non overlapping intervals of them such that total weight is maximum.
This one was from Graph, about MinCut standard problem. It was like, Country has n cities connected by m Bidirectional roads. May be multiple roads between pair of cities, country is connected. Importance of road (weight) Separation between 2 cities a,b = min possible sum of roads importance that needs to be removed to make a,b disconnected
Find product of separation value over all unordered pairs of cities % 10^9+7.
This problem is same as
https://www.hackerrank.com/challenges/road-network/problem
Solution :
Just use sliding window with extra space to keep the frequency. And overall complexity will be O(N)
Sort the given intervals according to start time, and when equal then by finish time. Keep a set of pairs of {curr_start_time, maximum weight with start_time >= curr_start_time}, which will store {u, w}, u as start time and w as maximum weight if we consider [i, n] subarray. Now iterate from back, and if you want to choose current pair{x,y,w} as one of the two, then find the lower_bound of y + 1 in the set , and update the answer accordingly. Just be catious in inserting a pair in set.
Its a standard algorithm problem, just use Ford Fulkerson algorithm with some modification. May be seeing the Editorial would give you more understanding.