Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- using System;
- using System.Collections.Generic;
- using System.Linq;
- public class Program
- {
- public static List<KittenNode> nodes = new List<KittenNode>();
- public static List<KittenNode> nodesStartTime = new List<KittenNode>();
- public static List<KittenNode> result = new List<KittenNode>();
- public static void Main()
- {
- nodes = new List<KittenNode>();
- //Accept input for kittens and beds.
- string[] startingConditions = Console.ReadLine().Split(new char[] { ' ' }, StringSplitOptions.None);
- int kittens = int.Parse(startingConditions[0]), beds = int.Parse(startingConditions[1]);
- //Initialize node list
- for (int i = 0; i < kittens; i++)
- {
- string[] demand = Console.ReadLine().Split(new char[] { ' ' }, StringSplitOptions.None);
- KittenNode newNode = new KittenNode(int.Parse(demand[0]), int.Parse(demand[1]), null);
- nodes.Add(newNode);
- }
- //Sort nodes by ascending exit times
- nodes = nodes.OrderBy(o => o.exitTime).ToList();
- //Sort nodesStartTime by ascending start times
- nodesStartTime = nodes.OrderBy(o => o.arrivalTime).ToList();
- CacheIntersectionResults();
- int catCount = 0;
- //Count the cats that fit into each bed and add them together.
- for (int i = 0; i < beds; i++)
- {
- KittenNode startingNode = FindOptimalNode(nodes, nodesStartTime, beds - i);
- catCount += CountCats(startingNode, beds - i);
- }
- //Output amount of cats.
- Console.WriteLine(catCount);
- Console.ReadLine();
- }
- public static int CountCats(KittenNode startingNode, int consideredNodeCount)
- {
- //If no cats are left in nodes, return.
- if (startingNode.exitTime == int.MaxValue)
- return 0; //No more cats
- //If more cats exist in nodes, find optimal node path for this bed.
- FindOptimalNodePath(startingNode, new List<KittenNode>(nodes), new List<KittenNode>(nodesStartTime), consideredNodeCount);
- //Count the cats and remove them from 'nodes'.
- int catCount = result.Count;
- foreach (KittenNode resultNode in result)
- {
- nodes.Remove(resultNode);
- nodesStartTime.Remove(resultNode);
- //foreach (KittenNode node in nodes) // K * N^2
- //{
- // if (node.intersections != null && node.intersections.Contains(resultNode))
- // node.intersections.Remove(resultNode);
- //}
- }
- result.Clear();
- return catCount;
- }
- public static void FindOptimalNodePath(KittenNode current, List<KittenNode> tempNodes, List<KittenNode> tempNodesStartTime, int consideredNodeCount)
- {
- //Remove current node from consideration.
- tempNodes.Remove(current);
- tempNodesStartTime.Remove(current);
- //Add current node to result.
- result.Add(current);
- // Find and remove all unreachable nodes
- List<KittenNode> removeList = new List<KittenNode>();
- for (int i = 0; i < tempNodes.Count; i++)
- if (tempNodes[i].arrivalTime < current.exitTime)
- removeList.Add(tempNodes[i]);
- foreach (KittenNode node in removeList)
- {
- tempNodes.Remove(node);
- tempNodesStartTime.Remove(node);
- }
- //If no more potential nodes exist, go to next loop or exit.
- if (tempNodes.Count == 0)
- return;
- //If more potential nodes exist, keep searching for optimal path.
- else
- {
- current = FindOptimalNode(tempNodes, tempNodesStartTime, consideredNodeCount); //K^2
- FindOptimalNodePath(current, tempNodes, tempNodesStartTime, consideredNodeCount); //K*N*Log(N)
- }
- }
- public static void CacheIntersectionResults()
- {
- //For all considered nodes, count the amount of intersections for each.
- //Intersection is defined by the starting point of a given node falling between the starting point and end point of a considered node.
- for (int i = 0; i < nodes.Count; i++)
- {
- nodes[i].intersections = new List<KittenNode>();
- for (int j = 0; j < nodesStartTime.Count; j++)
- {
- if (nodes[i].arrivalTime < nodesStartTime[j].arrivalTime && nodes[i].exitTime > nodesStartTime[j].arrivalTime)
- nodes[i].intersections.Add(nodesStartTime[j]);
- else if (nodes[i].exitTime < nodesStartTime[j].arrivalTime)
- break;
- }
- }
- }
- public static KittenNode FindOptimalNode(List<KittenNode> nodes, List<KittenNode> nodesStartTime, int consideredNodeCount)
- {
- //If no more nodes exist, return invalid node.
- if (nodes.Count == 0)
- return new KittenNode(0, int.MaxValue, null);
- //If amount of beds exceed amount of kittens or only one bed is available, return the lowest exit time.
- else if (nodes.Count < consideredNodeCount || consideredNodeCount == 1)
- return nodes[0];
- KittenNode currentNode = new KittenNode(0, int.MaxValue, null);
- int highestIntersectionCount = -1;
- //Iterate through intersections to find the highest amount.
- for (int i = 0; i < consideredNodeCount; i++)
- if (nodes[i].intersections.Count > highestIntersectionCount)
- {
- highestIntersectionCount = nodes[i].intersections.Count;
- //If two nodes have the same amount of intersections, select the one with lowest exit time. (Happens automatically due to sorting of 'nodes' list)
- currentNode = nodes[i];
- }
- return currentNode;
- }
- public class KittenNode
- {
- public KittenNode(int arrivalTime, int exitTime, List<KittenNode> intersections)
- {
- this.arrivalTime = arrivalTime;
- this.exitTime = exitTime;
- this.intersections = intersections;
- }
- public List<KittenNode> intersections;
- public int arrivalTime, exitTime;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement